概要

比赛地址

2020 Multi-University Training Contest 8

题目

1012. Linuber File System

题意大意

给你一颗树，可以对每棵树增加权值，同时更新其子树权值，问最少进行多少次操作使得所有的节点权值均在 [l[i],r[i]] 区间内。

解题思路

首先对所有 l,r 离散化之后，我们设 dp[i][j] 表示当前第 i 个节点转移到权值为 j 所需要最少操作，显然我们可以得出状态转移方程为 dp[i][j]=min(dp[i][j],\sum mi[j]-\sum (dp[u][j]==mi[j])) ，其中mi[i]=min(dp[i][j]) ，最后对于1号节点，我们要特殊处理1号节点不进行任何操作的答案，其次，对于所有1号节点的 l[1],r[1] ，ans=min(ans,dp[1][j]) 即可得出答案。

时间复杂度：O(Tn^2)

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e3+10;
vector<int> v[maxn];
int dp[maxn][maxn];
int l[maxn],r[maxn];
int sum[maxn];
int mi[maxn];
int n;
void dfs(int x,int fa)
{
    sum[x]=0;
    for(int i:v[x])
    {
        if(i==fa) continue;
        dfs(i,x);
        sum[x]+=mi[i]+1;
    }
    for(int i=l[x];i<=r[x];i++)
    {
        dp[x][i]=sum[x];
        for(int j:v[x])
        {
            if(j==fa) continue;
            if(dp[j][i]==mi[j]) dp[x][i]--;
        }
    }
    mi[x]=maxn;
    for(int i=l[x];i<=r[x];i++) mi[x]=min(mi[x],dp[x][i]);
}
void solve()
{
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=2*n+2;j++) dp[i][j]=maxn;
    }
    vector<int> vv;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d%d",&l[i],&r[i]);
        vv.push_back(l[i]);
        vv.push_back(r[i]);
    }
    vv.push_back(0);
    sort(vv.begin(),vv.end());
    vv.resize(unique(vv.begin(),vv.end())-vv.begin());
    for(int i=1;i<=n;i++)
    {
        l[i]=lower_bound(vv.begin(),vv.end(),l[i])-vv.begin();
        r[i]=lower_bound(vv.begin(),vv.end(),r[i])-vv.begin();
    }
    dfs(1,0);
    int ans=dp[1][lower_bound(vv.begin(),vv.end(),0)-vv.begin()];
    for(int i=l[1];i<=r[1];i++) ans=min(ans,dp[1][i]+1);
    printf("%d\n",ans);
    for(int i=1;i<=n;i++) v[i].clear();
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}