蒟蒻CSY又回来填坑啦~这次学树形DP，挑水题做

P2016 战略游戏

事实证明不应该先做封锁阳光大学那道题.....不然看什么题都像那个

树形DP，随便选个起点跑，对于起点的每个儿子有：

//f[现在所在点][1->这个点亮 0->这个点不亮]//初始态f[x][1]=1f[x][1] += min(f[to][0],f[to][1]);f[x][0] += f[to][1];

接下来的事情就简单了 递归跑一边 1500不怕爆栈

#include
     
      using namespace std;const int MAXN = 1510;struct EDGE{    int to,nxt;}edge[MAXN * 2];int head[MAXN],ectr; void addedge(int from,int to){ edge[++ectr].to = to; edge[ectr].nxt = head[from]; head[from] = ectr; } int n,m,f[MAXN][2]; void DP(int x,int y){ f[x][1] = 1,f[x][0] = 0; for(int i=head[x];i;i=edge[i].nxt){ int to = edge[i].to; if(to == y) continue; DP(to,x); f[x][1] += min(f[to][0],f[to][1]); f[x][0] += f[to][1]; 　　　　//notice in tree here must be += but =  } return ; } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++){ int now,k; cin>>now>>k; for(int j=1;j<=k;j++){ int to; cin>>to; addedge(now,to); addedge(to,now); } } DP(0,-1); cout<
      
       <
      
     

 

P1122 最大子树和

题目告诉你他是一个树形DP了，而且求的还是子树和

跑一个很容易的DP，比较舒服

但没考虑起点时玩了一次样例发现错了，WHY？

因为如果选一个固定点为根（比如1），其实也就规定了这个点必须选，但是这个点实际上并不是必需选的

所以应该在每次递归时维护完一个答案之后用ans立刻与f[x]取MAX

蒟蒻的AC代码竟然是以最大点为根...洛谷数据真的水....

下面贴正确AC代码

#include
     
      using namespace std;const int MAXN = 16010;int x,y,a[MAXN],n;struct EDGE{    int to,nxt;}edge[MAXN * 2];int head[MAXN],ectr = 1;void addedge(int from,int to){    edge[++ectr].to = to;    edge[ectr].nxt = head[from];    head[from] = ectr;}int f[MAXN],ans;void DP (int x,int y){    f[x] = a[x];    for(int i=head[x];i;i=edge[i].nxt){        int to = edge[i].to ;        if(to == y) continue;        DP(to,x);        f[x] += max(0,f[to]);    }    ans = max(ans,f[x]);    return ;}int main(){    ios::sync_with_stdio(false);    cin>>n;    a[0] = -0x3f3f3f3f;//     int st = 0;    for(int i=1;i<=n;i++){        cin>>a[i];//         if(a[i] > a[st]) st = i;    }    for(int i=1;i
      
       >x>>y;        addedge(x,y);        addedge(y,x);    }    DP(1,-1);    cout<
       
        <
       
      
     

持续更新

TAG：SIN_XIII ⑨