RQNOJ 188 购物问题：树形dp

题目链接：https://www.rqnoj.cn/problem/188

题意：

　　商场以超低价格出售n个商品，购买第i个商品所节省的金额为w[i]。

　　为了防止亏本，有m对商品是不能同时买的。但保证商品关系不出现环，不会出现如：(1,2) , (2,4) , (1,4)。

　　问你最多能节省的金额。

题解：

　　简直和POJ 2342 Anniversary party像极了(*/ω＼*)

　　将不能同时买的商品间连一条无向边。

　　所以子节点和父节点不能同时选。

　　唯一不同的是POJ是一棵树，而这道题是一片森林。需要对于每一棵树分别求dp，然后求和。

　　表示状态：

　　　　dp[i][j] = max discount

　　　　i：考虑到第i个商品（节点i）

　　　　j：是否选节点i　(j == 0 / 1)

　　找到答案：

　　　　ans = ∑ max(dp[root[i]][0],dp[root[i]][1])　（root[i]为每棵树的根）

　　如何转移：

　　　　dp[i][1] = sigma dp[son][0]　　　　（选父节点）

　　　　dp[i][0] = sigma max dp[son][0/1]　（不选父节点）

　　　　在dfs中：

　　　　　　dp[now][1] = w[i]

　　　　　　dfs(nex...)

　　　　　　dp[par][1] += dp[now][0]

　　　　　　dp[par][0] += max(dp[now][0], dp[now][1])

　　边界条件：

　　　　dp[i][1] = w[i]　（至少选自己）

　　　　dp[i][0] = 0

AC Code:

 // state expression:

 // dp[i][j] = max discount

 // i: considering ver i

 // j: whether to select j ver

 //

 // find the answer:

 // max dp[root][0/1]

 //

 // transferring:

 // dp[i][1] = sigma dp[son][0]

 // dp[i][0] = sigma max dp[son][0/1]

 // dfs:

 // dp[now][1] = w[i]

 // dfs(nex...)

 // dp[par[now]][1] += dp[now][0]

 // dp[par[now]][0] += max(dp[now][0], dp[now][1])

 //

 // boundary:

 // dp[i][1] = w[i]

 // dp[i][0] = 0

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 #define MAX_N 1005

 using namespace std;

 int n,m;

 int a,b;

 int ans;

 int w[MAX_N];

 int dp[MAX_N][];

 bool vis[MAX_N];

 vector<int> edge[MAX_N];

 void read()

 {

     cin>>n>>m;

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

     {

         cin>>w[i];

     }

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

     {

         cin>>a>>b;

         edge[a].push_back(b);

         edge[b].push_back(a);

     }

 }

 void dfs(int now,int par)

 {

     vis[now]=true;

     dp[now][]=w[now];

     for(int i=;i<edge[now].size();i++)

     {

         int temp=edge[now][i];

         if(temp!=par) dfs(temp,now);

     }

     if(par!=-)

     {

         dp[par][]+=dp[now][];

         dp[par][]+=max(dp[now][],dp[now][]);

     }

 }

 void solve()

 {

     memset(dp,,sizeof(dp));

     memset(vis,false,sizeof(vis));

     ans=;

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

     {

         if(!vis[i])

         {

             dfs(i,-);

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

         }

     }

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

RQNOJ 188 购物问题：树形dp

最新文章

热门文章