【Codeforces 815C】Karen and Supermarket

相关链接

题目传送门:http://codeforces.com/contest/815/problem/C

解题报告

这题就是考察树DP优化复杂度的一种常用技巧
考虑暴力DP的话,复杂度是:$O(n^3)$的
但如果在父亲结点那里记录一个儿子节点的子树大小的前缀和,复杂度就变成了$O(n^2)$
证明也很简单,对于任意两个结点,只会在$LCA$处产生$1$的花费

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;
const LL INF = 1e14;

int n, head[N], nxt[N], to[N], sz[N];
LL b, f[N][N], g[N][N], c[N], d[N], t1[N], t2[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;	
}

inline void relax(LL &a, LL b) {
	a = a > b? b: a;
}

inline void DFS(int w) {
	f[w][0] = g[w][0] = 0;
	for (int i = head[w]; i; i = nxt[i]) {
		DFS(to[i]);
		memcpy(t1, f[w], sizeof(t1));
		memcpy(t2, g[w], sizeof(t2));
		for (int j = 0; j <= sz[w]; j++) {
			for (int k = 0; k <= sz[to[i]]; k++) {
				relax(f[w][j + k], t1[j] + f[to[i]][k]);
				relax(g[w][j + k], t2[j] + g[to[i]][k]);
			}
		}
		sz[w] += sz[to[i]];
	}
	sz[w]++;
	for (int i = sz[w] - 1; ~i; i--) {
		g[w][i + 1] = g[w][i] + c[w] - d[w];
		relax(f[w][i + 1], f[w][i] + c[w]);
		relax(g[w][i + 1], f[w][i + 1]);
	}
	g[w][0] = 0;
}

int main() {
	n = read(); b = read();
	c[1] = read(); d[1] = read();
	for (int i = 2; i <= n; i++) {
		c[i] = read(); d[i] = read();
		AddEdge(read(), i);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			f[i][j] = g[i][j] = INF;
		}
	}
	DFS(1);
	for (int i = n; ~i; i--) {
		if (g[1][i] <= b) {
			printf("%d\n", i);
			exit(0);
		}
	}
	return 0;
}

【日常小测】tree

题目大意

给定一棵大小为$n(n \le 3000)$的树,带边权
请你给出一个长度为$k(k \le n)$的序列$\{a_i\}$
要求序列中两两元素不同,请你最小化$\sum\limits_{i=1}^{k-1}{dis(a_i,a_{i+1})}$

解题报告

我们看一看这个式子可以发现实际上是要我们给出一个大小为$k$的连通块
问你这个连通块内的边权乘上$2$再减掉直径的最小值是多少

于是我们定义$h_{i,j}$为$i$的子树中选$j$个点,还没有考虑直径的最小花费
$f_{i,j}$表示在$i$的子树里,选$j$个点,直径包含$i$的最小花费
$g_{i,j}$表示在$i$的子树里,选$j$个点,已经考虑过直径且直径不包含$i$的最小花费
然后我们暴力$DP$就可以了

我们的时间复杂度是$T(n)=\sum\limits_{i}{\sum\limits_{fa_i=fa_j}{size_i \cdot size_j}}$
仔细想一想的话,每一堆点只会在$LCA$处被计算,时间复杂度是$O(n^2)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3009;
const int M = N << 1;
const LL INF = 1e18;

int n,k,head[N],nxt[M],to[M],cost[M],sz[N];
LL vout=INF,f[N][N],g[N][N],h[N][N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void update(int w, int fa) { 
	fill(f[w], f[w]+1+N, INF);
    fill(g[w], g[w]+1+N, INF);
	fill(h[w], h[w]+1+N, INF);
	f[w][1] = g[w][1] = h[w][1] = 0; sz[w] = 1;
	for (int i=head[w],t;i;i=nxt[i]) {
		if ((t=to[i]) != fa) {
			update(to[i], w); 
			for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
				for (int j=1;j<=sz[t];j++) {
					g[w][x+j] = min(g[w][x+j], g[w][x] + h[t][j] + tmp);
					g[w][x+j] = min(g[w][x+j], f[w][x] + f[t][j] + cost[i]);
					g[w][x+j] = min(g[w][x+j], h[w][x] + g[t][j] + tmp);
				}
			}
			for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
				for (int j=1;j<=sz[t];j++) {
					f[w][x+j] = min(f[w][x+j], h[w][x] + f[t][j] + cost[i]);
					f[w][x+j] = min(f[w][x+j], f[w][x] + h[t][j] + tmp);
				}
			} 
			for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
				for (int j=1;j<=sz[t];j++) 
					h[w][x+j] = min(h[w][x+j], h[w][x] + h[t][j] + tmp);
			} 
			sz[w] += sz[t];
		}	
	}
	vout = min(vout, f[w][k]);
	vout = min(vout, g[w][k]); 
}

int main() {
	n = read(); k = read();
	for (int i=2,u,v;i<=n;i++) {
		u = read(); v = read();
		AddEdge(u, v, read());
	}
	update(1, 1);
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 4753】[JSOI2016] 最佳团体

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4753
神犇题解Ⅰ:http://blog.csdn.net/a_crazy_czy/article/details/51761871
神犇题解Ⅱ:http://blog.csdn.net/WorldWide_D/article/details/51565773

解题报告

考虑分数规划的套路的话,先二分一个值
现在问题变成了:在树上选一些点,使得点权和大于等于0
但这题还有一个奇怪的要求:一个点被选,其所有祖先必须被选

这就需要一个姿势非常奇怪的DP:

先将树搞到DFS序上去,设 $r(i)$ 表示第i个点的子树中DFS序最大的那个点
设 $f(i,j)$ 表示处理到了第$i$个点,已经选择了$j$个点
那么转移分两种:

  1. 选择第i+1个点:$f(i+1,j+1) = f(i+1,j+1) + f(i,j) + w_{i+1}$
  2. 不选择第i+1个点:$f(r(i+1)+1,j) = f(r(i+1)+1,j) + f(i,j)$

这样相当于如果不选择第$i$个点的话,就强行跳过他的子树
妙,真是太妙了!

【BZOJ 1040】[ZJOI2008] 骑士

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1040
数据生成器:http://paste.ubuntu.com/23618220/
神犇题解:http://blog.csdn.net/popoqqq/article/details/39748135

题解

看到这个题,感觉除了网络流之外别无他法
结果这货是个基环森林啊!
I well vegetable are!

这个问题搬到树上去大家都会做
原题好像叫“没有上司的舞会”?
考虑给树加上一条边之后会发生什么变化:
这条非树边要么两段的点选一个,要么都不选
于是特殊处理一下,跑三遍树上DP就可以辣!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const int M = N << 1;

int head[N],to[M],nxt[M];
int n,val[N],aim[N],tag[N],lb,rb;
LL vout,f[N][2];

inline void Add_Edge(const int u, const int v) {
	static int T = 1;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

void DFS(int w, int f) {
	tag[w] = 1; 
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f && to[i]) {
		if (tag[to[i]]) {
			lb = w; rb = to[i];
			to[i] = to[i^1] = 0;
		} else {
			DFS(to[i], w);
		}
	}
}
 
void solve(int w, int fa) {
	f[w][0] = 0;
	f[w][1] = val[w];
	for (int i=head[w];i;i=nxt[i]) if (to[i] && to[i] != fa) {
		solve(to[i], w);
		f[w][1] += f[to[i]][0];
		f[w][0] += max(f[to[i]][1],f[to[i]][0]);
	}
	if (tag[w] == 2) {
		f[w][0] = 0;
	} else if (tag[w] == 3) {
		f[w][1] = 0;
	}
}
 
int main(){
	n = read();
	for (int i=1,t;i<=n;i++) {
		val[i] = read();
		if (aim[t=read()] != i) {
			Add_Edge(i, t);
			aim[i] = t;
		}
	}
	for (int i=1;i<=n;i++) {
		if (!tag[i]) {
			LL tmp; 
			lb = rb = 0;
			DFS(i,i);
			
			tag[lb] = 2; tag = 3;
			solve(i,i);
			tmp = max(f[i][0], f[i][1]);
			
			tag[lb] = 3; tag = 2;
			solve(i,i);
			tmp = max(tmp, max(f[i][0], f[i][1]));
			
			tag[lb] = 3; tag = 3;
			solve(i,i);
			tmp = max(tmp, max(f[i][0], f[i][1]));
			vout += tmp;
		}
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 2286】[Sdoi2011] 消耗战

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2286
数据生成器:http://paste.ubuntu.com/23372796/

就是把虚树建出来了以后,在虚树上跑树上DP
DP很好想,只需要会建虚树就可以辣!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int SGZ = 18;
const int M = 500000+9;
const int N = 250000+9;
const int INF = 0x7fffffff;

int head[N],nxt[M],to[M],cost[M],dep[N],fa[N][SGZ],MN[N][SGZ];
int n,m,p[N],num[N],stk[N],top,tot,T;
bool vis[N]; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline void Add_Edge(int u, int v, int w) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f) {
	static int dfs_cnt = 0; num[w] = ++dfs_cnt;
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
			MN[to[i]][0] = cost[i];
		}
	}
}

inline bool CMP(const int &x, const int &y) {
	return num[x] < num[y];
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
} 

inline int Get_Cost(int w, int pur) {
	int ret = INF; pur = dep[pur];
	for (int i=17;~i;i--) {
		if (dep[fa[w][i]] >= pur) {
			ret = min(ret, MN[w][i]);
			w = fa[w][i];
		}
	}
	return ret;
}

inline void build() {
	stk[top = 1] = 1;
	for (int i=1,w,lca;i<=m;i++) {
		w = p[i]; lca = LCA(stk[top], w);
		while (dep[stk[top]] > dep[lca]) {
			if (dep[stk[top-1]] <= dep[lca]) 
				Add_Edge(lca, stk[top]);
			else 
				Add_Edge(stk[top-1], stk[top]);
			--top;
		}
		if (stk[top] != lca) stk[++top] = lca, p[++tot] = lca;
		stk[++top] = w;
	}
	for (int i=1;i<top;i++) 
		Add_Edge(stk[i], stk[i+1]);
}

inline LL DP(int w, int f) {
	LL tmp = 0;
	for (int i=head[w];i;i=nxt[i]) 
		tmp += DP(to[i], w);
	if (vis[w]) return Get_Cost(w, f);
	else if (w != 1) return min((LL)Get_Cost(w, f), tmp);
	else return tmp;
}

int main() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	
	DFS(1, 1); MN[1][0] = INF;
	for (int j=1;j<=17;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
			MN[i][j] = min(MN[i][j-1], MN[fa[i][j-1]][j-1]);
		}
	} 
	
	memset(head,0,sizeof(head));
	for (int k=read();k;k--) { 
		m = tot = read(); T = 0; 
		for (int i=1;i<=m;i++) vis[p[i] = read()] = 1;
		sort(p+1, p+1+m, CMP);
		build();
		printf("%lld\n",DP(1,1)); head[1] = 0;
		for (int i=1;i<=tot;i++) vis[p[i]] = 0, head[p[i]] = 0;
	}
	return 0;
}

【BZOJ 3829】[POI2014] FarmCraft

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3829

来来来,让我们来%Claris:http://www.cnblogs.com/clrs97/p/4403170.html

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

const int N = 500000+9;
const int M = 1000000+9;

int head[N],nxt[M],to[M],g[N],f[N];
int n,tmp[N],beg[N],end[N],tot,C1;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

inline bool CMP(const int &a, const int &b) {
	return max(f[a],g[a]+2+f[b]) < (f[b],g[b]+2+f[a]);
}

void DP(int w, int fa) {
	int cnt = 0;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != fa) cnt++;
	}
	beg[w] = tot + 1; 
	end[w] = (tot += cnt); cnt = -1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != fa) {
		DP(to[i],w);
		g[w] += g[to[i]] + 2;
		tmp[beg[w]+(++cnt)] = to[i];
	}
	if (beg[w] <= end[w]) {
		sort(tmp+beg[w],tmp+end[w]+1,CMP);
	}
	for (int i=beg[w],sum=0;i<=end[w];i++) {
		f[w] = max(f[w], f[tmp[i]] + sum + 1);
		sum += g[tmp[i]] + 2;
	}
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		f[i] = read();
	}
	C1 = f[1];
	for (int i=1;i<n;i++) {
		Add_Edge(read(),read());
	}
	DP(1,1);
	printf("%d\n",max(g[1]+C1,f[1]));
	return 0;
}