HDU6866 Linuber File System

题目大意

题目链接

给定一棵\(n\)个节点的有根树,\(1\)号节点是根。每个点有一个参数,初始时为\(0\)。

你可以进行若干次操作。每次操作你指定一个节点\(u\)和一个整数\(x\)(可以为负),令\(u\)的子树内(包含\(u\))所有节点的参数加上\(x\)。

给你\(n\)个区间\([l_i,r_i]\),问最少进行多少次操作,可以使每个节点\(i\)的参数都在自己的\([l_i,r_i]\)范围内。

数据范围:\(1\leq n\leq 2000,-10^9\leq l_i\leq r_i\leq 10^9\)。\(T\)组测试数据,\(T\leq 10\)。

本题题解

首先,容易发现,在同一个节点上,我们最多只会进行一次操作。于是问题转化为,给每个节点确定一个“操作值”,使得【\(i\)及\(i\)的所有祖先的操作值之和】在\([l_i,r_i]\)范围内,同时最小化“操作值”不为\(0\)的节点数量。

考虑树形DP。设\(dp[u][x]\)表示,如果节点\(u\)的所有祖先(不包含它自己。如无特殊说明,以下所说的祖先都不包含自己,子树都包含自己)操作值之和为\(x\),在\(u\)的子树内,最少还要再进行多少次操作。显然,子树内的操作,不会影响到子树外的其他点,且这个子树内的答案只受它的祖先影响(这个影响就是\(x\),我们把我们无法确定的东西都写到状态里),所以这个状态很合理。

考虑转移。显然,对于\(u\)的所有儿子来说,它们的祖先对它们的贡献是相同的。所以可以预处理一个\(g[u][y]=\sum_{v\in\text{son}(u)}dp[v][y]\)。

对于\(u\)的儿子来说,这个\(y\)是它的祖先对它的贡献之和。对\(u\)来说,这个\(y\)是它自己的“操作值”加上它祖先的操作值之和(也就是说,\(y\)比前面的\(x\),就是多了一个\(u\)自己的“操作值”)。并且,\(y\)就是\(u\)最终的参数,所以合法的\(y\)必须在\([l_u,r_u]\)之间。于是我们能写出转移式:

\[dp[u][x]=\min_{l_u\leq y\leq r_u}\{g[u][y] + [y\neq x]\} \]

可以对第二维,在\(l,r\)区间里的部分求前缀、后缀最小值。则转移就是\(O(1)\)的了(具体可以见我代码)。时间复杂度\(O(n\cdot \text{值域})\)。最终答案就是\(dp[u][0]\)。

但是由于值域高达\(10^9\),这个做法目前还不可行。为了继续优化,需要用到一个观察:

引理:一定存在一种最优解,使得每个节点最终的参数(它和它所有祖先的“操作值”之和)属于集合\(\{l_i,r_i | 1\leq i\leq n\}\)。

证明可以考虑,设把所有\(l_i,r_i\)放在一起排序后,设这些值为\(w_1\dots w_{2n}\)。对于任意一个\(x\),假设\(w_j<x<w_{j+1}\),那么\(dp[u][x]\)的值一定等于\(dp[u][w_j]\)。这个好像可以归纳。

由这个引理,有一个直接的推论就是,存在一种最优解,使得所有的\(x,y\),都在\(\{l_i,r_i | 1\leq i\leq n\}\cup\{0\}\)这个集合里(\(x\)可能是\(0\),因为你可以认为\(1\)的祖先的参数是\(0\))。所以直接把这些点离散化,就可以\(O(n^2)\) DP了。

参考代码:

//problem:1012
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}

const int MAXN=2000;
const int INF=1e9;
int n;
struct EDGE{int nxt,to;}edge[MAXN*2+5];
int head[MAXN+5],tot;
inline void add_edge(int u,int v){edge[++tot].nxt=head[u],edge[tot].to=v,head[u]=tot;}

struct Range_t{
	int l,r;
}rg[MAXN+5];
int vals[MAXN*2+5],cnt_val;
int f[MAXN+5][MAXN*2+5],pre[MAXN*2+5],suf[MAXN*2+5];
void dfs(int u,int fa){
	for(int i=1;i<=cnt_val;++i){
		f[u][i]=0;
	}
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
		for(int j=1;j<=cnt_val;++j){
			f[u][j]+=f[v][j];
		}
	}
	int l=lob(vals+1,vals+cnt_val+1,rg[u].l)-vals;
	int r=lob(vals+1,vals+cnt_val+1,rg[u].r)-vals;
	pre[0]=suf[cnt_val+1]=INF;
	for(int i=1;i<=cnt_val;++i){
		pre[i]=min(pre[i-1],((i>=l && i<=r) ? f[u][i] : INF));
	}
	for(int i=cnt_val;i>=1;--i){
		suf[i]=min(suf[i+1],((i>=l && i<=r) ? f[u][i] : INF));
	}
	for(int i=1;i<=cnt_val;++i){
		f[u][i]=min(((i>=l && i<=r) ? f[u][i] : INF), min(pre[i-1],suf[i+1])+1);
	}
}
void solve_case(){
	cin>>n;
	for(int i=1;i<=n;++i){
		head[i]=0;
	}
	tot=0;
	for(int i=1;i<n;++i){
		int u,v;cin>>u>>v;
		add_edge(u,v);
		add_edge(v,u);
	}
	cnt_val=0;
	for(int i=1;i<=n;++i){
		cin>>rg[i].l>>rg[i].r;
		vals[++cnt_val]=rg[i].l;
		vals[++cnt_val]=rg[i].r;
	}
	vals[++cnt_val]=0;
	sort(vals+1,vals+cnt_val+1);
	cnt_val=unique(vals+1,vals+cnt_val+1)-(vals+1);
	dfs(1,0);
//	for(int i=1;i<=cnt_val;++i)cout<<vals[i]<<" ";cout<<endl;
//	for(int i=1;i<=n;++i){
//		for(int j=1;j<=cnt_val;++j)cout<<f[i][j]<<" ";cout<<endl;
//	}
	int pos=lob(vals+1,vals+cnt_val+1,0)-vals;
	cout<<f[1][pos]<<endl;
}
int main() {
	int T;cin>>T;while(T--)solve_case();
	return 0;
}
上一篇:基于线性探测法的散列表


下一篇:损失函数相关