动态规划训练第一阶段（for初学者） - c++编程基础

始值赋为1，那么儿子节点就不能取了，所以dp[i][1]=sigma(dp[j][0]);

判断方案是否唯一

观察状态转移的过程可知：dp[i][0]是由dp[j][0],dp[j][1]两个状态过来的，所以当dp[j][0]==dp[j][1]时，方案不唯一，即子节点选与不选都可以
但是注意前提是dp[i][0]更优与dp[i][1]，即i这个节点肯定被选择了，否则状态就仅仅由dp[j][1]转移而来，不能判断不唯一。

[cpp]
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define max(a,b) a>b a:b
const int maxn = 201;
vector edge[maxn];
int dp[210][2];
void dfs(int u,int p)
{
int i,j;
dp[u][1]=1;
dp[u][0]=0;
for(i=0;i {
int v=edge[u][i];
if(v==p) continue;
dfs(v,u);
dp[u][1]+=dp[v][0];
dp[u][0]+=max(dp[v][0],dp[v][1]);
}
}
int main(){
map mm;
int n,i,tot;

char bos[110],a[110],b[110];
while(scanf("%d",&n),n)
{
tot=0;
for(i=0;i<=200;i++) edge[i].clear();
mm.clear();
scanf("%s",bos);mm[bos]=tot++;
for(i=0;i {
scanf("%s%s",a,b);
if(mm.find(a)==mm.end()) mm[a]=tot++;
if(mm.find(b)==mm.end()) mm[b]=tot++;
edge[mm[b]].push_back(mm[a]);
}
dfs(0,0);bool flag=true;
for(i=0;i {
flag=true;
if(dp[i][0]>dp[i][1])
{
for(int j=0;j {
if(dp[edge[i][j]][0]==dp[edge[i][j]][1])
{
flag=false;
break;
}
}
}
if(!flag) break;
}
printf("%d",max(dp[0][0],dp[0][1]));
if(dp[0][0]==dp[0][1]||!flag) printf(" No\n");
else printf(" Yes\n");
}
return 0;
}

作者：haha593572013

动态规划训练第一阶段（for初学者）(四)