由于换季，商场推出优惠活动，以超低价格出售若干种商品。但是商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。经过仔细研究，我们发现商场出售的超低价商品中，不存在以下这种情况：n(n>=3)种商品C1，C2，C3，……，Cn，其中Ci和Ci+1是不能同时购买的（i=1,2,……,n-1），而且C1和Cn也不能同时购买。
请编程计算可以节省的最大金额数。
对于这种完全没有思路的题，还是先多看题目吧。忽然发现有一个有意思的条件： 不存在以下这种情况：n(n>=3)种商品C1，C2，C3，……，Cn，其中Ci和Ci+1是不能同时购买的（i=1,2,……,n-1)，即为不存在连续>=3个的不能连续购买，且不会有环。
接着重新分析题目，一个点连了一个不能购买的点，这个不能购买的点又连了一个不能购买的点，再加上刚刚所分析的特殊条件，那么我们便可以发现，题目所给的限制条件是一个类似于树形结构了，且对于每一个树上的子节点与父节点，只能选一个。
这时就可以构造状态了，dp[i][1/0]表示第i个点选或不选，从下向上更新答案，也就没有了后效性。
接着可以考虑转移，从一棵树上如果这个点选了，那么只能从它子节点里没有选的转移过来，如果这个节点没有选，那么它的子节点选或不选都是可以的。
对于代码的实现部分，细节的一点是要注意题目是一个森林结构，所以在枚举每一个点时，也要确定建树的点没有重复。DFS的建树后，注意自底向上建树即可。特别的，如果这个点和任何一个点都没有边，那么它肯定是要选的。
下附AC代码。
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<vector> #define maxn 1005 using namespace std; int n,k; int ans=0; int val[maxn]; int vis[maxn]; int flag[maxn]; int dp[maxn][10]; vector<int> edge[maxn]; vector<int> nex[maxn]; void dfs(int now) { vis[now]=1; int len=edge[now].size(); for(int i=0;i<len;i++) if(vis[edge[now][i]]==0) { nex[now].push_back(edge[now][i]); dfs(edge[now][i]); } } void findans(int now) { int len=nex[now].size(); if(len==0) { dp[now][1]=val[now]; dp[now][0]=0; return; } for(int i=0;i<len;i++) findans(nex[now][i]); for(int i=0;i<len;i++) { int ne=nex[now][i]; dp[now][1]+=dp[ne][0]; dp[now][0]+=max(dp[ne][1],dp[ne][0]); } dp[now][1]+=val[now]; return; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&val[i]); } for(int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); edge[x].push_back(y); edge[y].push_back(x); } for(int i=1;i<=n;i++) { if(edge[i].size()==0) { vis[i]=1; ans+=val[i]; } else if(vis[i]==0) { dfs(i); findans(i); ans+=max(dp[i][0],dp[i][1]); } } printf("%d\n",ans); }
