首页 > 代码库 > POJ 1770 树形DP
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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。