davidwang's Blog

首先这样一道题我这样的蒟蒻肯定是不会的了

只有卢爷很快就能秒掉这种题目拉

下面是我们的对话：

 “卢爷，4160怎么做？”

“4160,什么题阿？”于是打开bzoj开始翻"哦，这道题阿，我也不会做"

"那您是怎么A掉的？" "就是随便猜了个性质，就是求出独立集覆盖就可以了"

“为什么？” “你感受以下就是可以的”

于是我感受了一下

然后就没了

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <deque>
#include <iostream>
using namespace std;
#define LL long long
#define X first
#define Y second
template<typename T>
inline T sqr(const T &x){ return x*x; }
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 15;
int a[N][N];
int list[200];
int f[1<<N],ok[1<<N];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int m=read(),n=0;
	char s1[3],s2[3];
	memset(list,-1,sizeof(list));
	for (int i=1;i<=m;i++){
		scanf("%s%s",s1,s2);
		if (list[s1[0]]==-1) list[s1[0]]=n++;
		if (list[s2[0]]==-1) list[s2[0]]=n++;
		int x=list[s1[0]],y=list[s2[0]];
		a[x][y]=a[y][x]=1;
	}
	for (int s=1;s<(1<<n);s++){
		ok[s]=1;
		for (int j=0;j<n;j++)
			if (s>>j&1)
				for (int k=0;k<n;k++)
					if (s>>k&1)
						if (a[j][k] || a[k][j])
							ok[s]=0;	
	}
	for (int s=1;s<(1<<n);s++){
		f[s]=100000;
		if (ok[s]){
			f[s]=1; continue;
		}
		for (int s0=(s-1)&s;s0;s0=(s0-1)&s){
			if (ok[s0] && f[s^s0]<f[s]) f[s]=f[s^s0]+1;
		}
	}
	printf("%d\n",f[(1<<n)-1]-2);
	return 0; 
}

这是一类非线性的树形DP问题，首先我们想到F[i][s][j]表示以i为根的子树考虑了S中的儿子有j个黑点的答案

然后我们发现DP起来很有问题因为我们要考虑每一个子树的情况

首先利用背包的性质来进行DP 这样可以少去Sz这一为状态，空间就没有问题了

然后我们发现复杂度是这么一个东西

$$  Sum_x(size[x] * Sum_{y|y是x排在前面的兄弟}size[y])  $$

然后这个东西的复杂度是 $$ O(n^2) $$ 的具体证明不会 但是感受一下二叉树，菊花树,  链什么的都没什么问题

所以就这样了

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ctime>
using namespace std;
#define LL long long
#define LD long double
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch>'9' || ch<'0';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 2010;
int to[N<<1],next[N<<1],len[N<<1],start[N],cnt,fa[N];
int q[N],size[N],k,n;
inline void connect(int x,int y,int z){
	to[++cnt]=y; next[cnt]=start[x];
	start[x]=cnt; len[cnt]=z;
}
LL f[N][N];
inline LL calc(int x,int i,int y,int j){
	return j * (k - j) + (size[y] - j) * (n - k - (size[y] - j));
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read(); k=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read(),z=read();
		connect(x,y,z);
		connect(y,x,z);
	}
	int head=0,tail=1,u,v;
	q[1]=1;
	memset(fa,-1,sizeof(fa));
	fa[1]=0;
	while (head<tail){
		u=q[++head];
		for (int p=start[u];p;p=next[p]){
			v=to[p];
			if (fa[v]==-1){
				q[++tail]=v;
				fa[v]=u;
			}
		}
	}
	for (int ii=n;ii;ii--){
		int x=q[ii];
		size[x]++;
		f[x][0]=f[x][1]=0;
		for (int p=start[x];p;p=next[p]){
			if (to[p]==fa[x]) continue;
			int y=to[p];
			for (int i=min(k,size[x]);i>=0;i--)
				for (int j=min(size[y],k-i);j>=0;j--)
					f[x][i+j]=max(f[x][i+j],f[x][i]+f[y][j]+calc(x,i,y,j)*len[p]);
			size[x]+=size[y];
		}
	}
	printf("%lld\n",f[1][k]);
}