POJ 1770 树形DP

咋一看确实想到的是树形DP，但是我一开始也马上想到环的情况，这样应该是不可以进行树形DP的，然后我自以为是地想用有向图代替无向图，而且总是从能量高的指向能量低的，这样自以为消除了环，但是其实是不对滴，这样的话在树形DP的过程中就会出问题。然后实在没想到好的方法，去看了下这题的discuss，结果大家都说数据不会有环，为什么呢，因为题目的隐含条件就是从一个状态到另一个状态有且只有一条路径，我又仔细看了下题目，找是找到了类似的话，说只能遵循这样的变化，但是不知道是我的认知跟别人不一样还是怎么回事，我感觉这个是题目里面的描述，只要他提供了这样多的能量，应该还是可以变化的啊。。

反正最后按普通的树形DP过是过了，就是这个题意有点莫名其妙，这个是区赛的题，难道考审题。。。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

int n,m;

vector<int> G[210];

int A[210],B[210];

int dp[210][2];

int vis[210];

void dfs(int x,int f)

{

    vis[x]=1;

    dp[x][1]=A[x];

    dp[x][0]=0;

    int r=G[x].size();

    for (int i=0;i<r;i++){

        if (G[x][i]==f) continue;

        dfs(G[x][i],x);

        int vx=G[x][i];

        dp[x][1]+=dp[vx][0];

        dp[x][0]+=max(dp[vx][0],dp[vx][1]);

    }

}

int main()

{

    while (scanf("%d%d",&n,&m))

    {

        if (n==0 && m==0) break;

        for (int i=1;i<=n;i++){

            scanf("%d",&A[i]);

            G[i].clear();

        }

        for (int i=1;i<=m;i++){

            scanf("%d",&B[i]);

        }

        memset(vis,0,sizeof vis);

        //memset(dp,0,sizeof dp);

        sort(A+1,A+1+n);

        for (int i=n;i>=1;i--){

            for (int j=i-1;j>=1;j--){

                //if (i==j) continue;

                for (int k=1;k<=m;k++){

                    if (abs(A[i]-A[j])==B[k]){

                        G[i].push_back(j);

                        G[j].push_back(i);

                    }

                }

            }

        }

        int ans=0;

        for (int i=1;i<=n;i++){

            if (!vis[i]){

                //cout<<i<<" qqq "<<endl;

                dfs(i,-1);

                ans+=max(dp[i][0],dp[i][1]);

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

POJ 1770 树形DP

最新文章

热门文章