题目描述 由于换季，商场推出优惠活动，以超低价格出售若干种商品。但是商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。经过仔细研究，我们发现商场出售的超低价商品中，不存在以下这种情况：n(n>=3)种商品C1，C2，C3，……，Cn，其中Ci和Ci+1是不能同时购买的（i=1,2,……,n-1），而且C1和Cn也不能同时购买。 请编程计算可以接生的最大金额数。 输入格式 第一行两个整数K，M（1<=K<=1000），其中K表示超低价商品数，K种商品的编号依次为1，2，3，……，K；M表示不能同时购买的商品对数。 接下来K行，第i行有一个整数Xi表示购买编号为i的商品可以节省的金额（1<=Xi<=100）。 再接下来M行，每行两个数A，B，表示A和B不能同时购买，1<=A,B<=K,A≠B。 输出格式 仅一行一个整数，表示能节省的最大金额数。
对我来说这题有点难，不过看见这个条件就能思考了： 不存在以下这种情况：n(n>=3)种商品C1，C2，C3，……，Cn，其中Ci和Ci+1是不能同时购买的（i=1,2,……,n-1)，即为不存在连续>=3个的不能连续购买，且不会有环。就可以发现这是一道TREEDP：dp[i][1/0]表示第i个点选或不选，从下向上更新答案，也就没有了后效性。
#include <iostream> #include <string.h> #include <algorithm> #include <vector> #include <stdio.h> #include <stack> #include <queue> #include <map> using namespace std; typedef long long ll; int n,m,x,y,c[20005]; vector<int> em[20005]; bool vis[20005]; int dp[20005][2]; int ans=0; void dfs(int now) { vis[now]=1; dp[now][1]=c[now]; int sz=em[now].size(); for(int i=0;i<sz;i++) { if(!vis[em[now][i]]) { dfs(em[now][i]); dp[now][1]+=dp[em[now][i]][0]; dp[now][0]+=max(dp[em[now][i]][0],dp[em[now][i]][1]); } } } int main(int argc, char const *argv[]) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&c[i]); } for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); em[x].push_back(y); em[y].push_back(x); } for(int i=1;i<=n;i++) { if(!vis[i]) { dfs(i); ans+=max(dp[i][0],dp[i][1]); } } printf("%d\n",ans); return 0; }