DP刷题（1500-1700）

1.DP+DFS+二分：https://codeforces.com/contest/1946/problem/C

首先不难想到二分一个x，那么我们如何check它呢？

我们令dfs(i,j,k)去找在i子树下最多可以分成>=k的连通块的个数，我们选1为根节点，对于它的子节点e，我们在去搜e子树的最好的划分，剩下的分给1，其他子节点同理，最后再看一看1连的连通块是否>=k即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int t;
int f[100010],n,k;
int v,u;
int cnt;
vector<int> edge[100010];
void dfs(int root,int fa,int ss){
	f[root]=1;
	for(int i=0;i<edge[root].size();i++){
		int x=edge[root][i];
		if(x==fa) continue;
		dfs(x,root,ss);
		f[root]+=f[x];
	}
	if(f[root]>=ss){
		cnt++;
		f[root]=0;
	}
}
bool check(int x){
	cnt=0;
	dfs(1,-1,x);
	if(cnt>=k+1) return 1;
	return 0;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>k;
		memset(edge,0,sizeof(edge));
		memset(f,0,sizeof(f));
		for(int i=1;i<=n-1;i++){
			cin>>u>>v;
			edge[u].push_back(v);
			edge[v].push_back(u);
		}
		
		int l=1,r=n;
		while(l<r){
			int mid=(l+r+1)/2;
			if(check(mid)==1) l=mid;
			else r=mid-1;
		}
		cout<<l<<endl;
	}
}

2.递推/DP：https://codeforces.com/contest/1957/problem/C

我们考虑最终的情况一定是每一行只有一个，每一列也只有一个。

其次，发现对于一个棋子将整个棋盘划分开再整合对于答案没有影响。

综上，我们先根据落点的不同整理出一个干净的棋盘，我们令f[i]表示i*i规模的放法。

当n>2 时，由于第一行和第一列一定会有棋子

假如放在左上角，就贡献f[i-1],剩下的2n-2中划分两行也就是f[i-2]，这样就得到递推公式了。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,k;
ll mod=1e9+7;
ll f[300010];
ll dfs(ll x){
	if(f[x]>0) return f[x];
	return f[x]=(dfs(x-1)+(2*x-2)*dfs(x-2)%mod)%mod;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=k;i++){
			ll r,c;
			cin>>r>>c;
			if(r==c) n-=1;
			else n-=2;
		}
		memset(f,0xc0,sizeof(f));
		f[1]=1,f[2]=3,f[0]=1;
		cout<<dfs(n)<<endl;
	}
}

3.DFS+博弈论：https://codeforces.com/contest/1970/problem/C2

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,t;
vector<int> edge[200010];
int u,v;
int root1;
int dfs(int root,int x,int fa){//x:0表示RON 
	if(edge[root].size()==1&&root!=root1){
		if(x==0) return 1;
		else return 0;
	}
	for(int i=0;i<edge[root].size();i++){
		int xx=edge[root][i];
		if(xx==fa) continue;
		if(dfs(xx,1-x,root)==x) return x;	
	}
	return 1-x;
}
int main(){
	cin>>n>>t;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	/*for(int i=1;i<=n;i++){
		for(int j=0;j<edge[i].size();j++) cout<<edge[i][j]<<" ";
		cout<<endl;
	} */

	cin>>root1;
	if(dfs(root1,0,-1)==0) cout<<"Ron";//0表示RON胜 
	else cout<<"Hermione";
}