RQNOJ 188 购物问题

题目描述

传送门

由于换季，商场推出优惠活动，以超低价格出售若干种商品。但是商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。经过仔细研究，我们发现商场出售的超低价商品中，不存在以下这种情况：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。

输出格式

仅一行一个整数，表示能节省的最大金额数。

样例

Input

3 1
1
1
1
1 2

Output

2

主要思路

此题一看便是dp（废话，人家RQNOJ都告诉你了），经过仔细观察，发现题目中存在这样一句话：

不存在以下这种情况：n(n>=3)种商品C1，C2，C3，……，Cn，其中Ci和Ci+1是不能同时购买的（i=1,2,……,n-1），而且C1和Cn也不能同时购买。

再结合那m种不能同时购买的情况，其实，这就是一道树上dp题目。
思路有了，问题来了：dp方程怎么搞？
通过观察发现，此题边无向，便成为了森林类的树上dp。
于是，dp方程便出来了：

这是最终实现时的代码，nex代表与now有边相连的点，
其中，按边扩展的dp[i][0]表示不选i及其子树的最大节省金额数
dp[i][1]则表示选择i及其子树的最大节省金额数
枚举i,求出每一个节点的dp[i][0]与dp[i][1]，求出其中的最大值，从而相加得到最终的答案。

代码如下

//如有不懂请参考注释，谢谢！
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <map>
#include <stack>
#include <cstring>
using namespace std;
#define ll long long
//请忽略上面的一切

vector <int> lin[10005];//代替邻接表，当时发现link在RQNOJ中是关键字，便改成了这样

int k,m,ans=0;
int a[1005];
int dp[1005][2];//根据前文介绍，第二维只需0、1两个下标即可
bool vis[100005];//判断该点是否被访问过

//披着dfs的dp
void dfs(int now,int pre)//pre用来检查是否重复走同一条边（因为无向）
{
    vis[now]=1;
    dp[now][0]=0;
    dp[now][1]=a[now];//由于选择其子树，即至少选择该节点
    int len=lin[now].size();//由该点出发能通向多少个点
    for(int i=0;i<len;i++)
    {
        int nex=lin[now][i];
        if(nex!=pre)//如果没有原路返回
        {
            dfs(nex,now);//搜索
            dp[now][0]+=max(dp[nex][0],dp[nex][1]);//如果不选择其子树，便可选择另一点的子树
            dp[now][1]+=dp[nex][0];//否则不行
        }
    }
}

int main(int argc, char const *argv[])
{
    memset(vis,0,sizeof(vis));//强迫症犯了...
    ios::sync_with_stdio(false);//流加速
    cin>>k>>m;
    for(int i=1;i<=k;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        lin[x].push_back(y);//由于是无向边（互不相容），需要添加两次
        lin[y].push_back(x);
    }
    for(int i=1;i<=k;i++)//一次对每个未被访问到的节点进行搜索，求出对应的dp[i][0]和dp[i][1]
        if(!vis[i])
        {
            dfs(i,-1);
            ans+=max(dp[i][0],dp[i][1]);
        }
    cout<<ans<<endl;
    return 0;
}

[RQNOJ] P188 购物问题

原文：https://www.cnblogs.com/wjsoj/p/12006426.html