[Acwing] 323. 战略游戏 树形dp

前言

传送门 :

思路

看完这道题,感觉和上司的舞会同理

状态表示 f [ i ] [ 2 ] f[i][2] f[i][2] 以当前 i i i为根的子树中

• 1 1 1 ，设置哨兵, 那么子树既可以设置 也 可以不设置
• 0 0 0 , 不设置哨兵, 那么子树必须设置

因此状态转移方程 :
f [ i ] [ 0 ] = f [ i ] [ 0 ] + f [ j ] [ 1 ] f[i][0] = f[i][0] + f[j][1] f[i][0]=f[i][0]+f[j][1]
f [ i ] [ 1 ] = f [ i ] [ 1 ] + m i n ( f [ j ] [ 0 ] , f [ j ] [ 1 ] ) f[i][1] = f[i][1] + min(f[j][0],f[j][1]) f[i][1]=f[i][1]+min(f[j][0],f[j][1])

Mycode

map mp;

const int N  = 1550;

int n;


bool st[N];
int dp[N][2];

void dfs(int u,vector g[]){
	dp[u][0] = 0 ;
	dp[u][1] = 1;
	
	for(auto j : g[u]){
		dfs(j,g);
		dp[u][0] += dp[j][1];
		dp[u][1] +=min(dp[j][0],dp[j][1]);
	}
}
void solve()
{
	vector g[n];
	memset(st,0,sizeof st);
	
	for(int i = 0 ;i>b;
			g[a].pb(b);
			st[b] = 1;//不是根节点
		}
	}
	
	int root = 0 ;
	while(st[root]) root++;
	dfs(root,g);
	cout