2018.8.17题解 2018暑假集训之纸牌

题面描述

---

 试题描述

小a和小b玩一个游戏，有n张卡牌，每张上面有两个正整数x,y。

取一张牌时，个人积分增加x，团队积分增加y。

求小a，小b各取若干张牌，使得他们的个人积分相等。

输入

第一行一个整数n。
接下来n行，每行两个整数x,y，用空格隔开。

输出

一行一个整数，
表示小a的积分和小b的积分相等的时候，团队积分的最大值。

输入示例

4
3 1
2 2
1 4
1 4

输出示例

10

其他说明

对于100%的数据，0<n<=100，1<x<=1e3，0<y<=1e6。

---

与这个题相比其实poj上有一个与本题类似但是更加经典的例题

本题乍一看很像一道经典的“取与不取”的01背包问题（x当作重量 y当作价值）但是仍然存在很多问题需要注意

1、如何解决二人同时取的问题？

首先我们来分析一下 由于数据较大避免mle 所以最多二维dp

但是本题中同时存在三个变量：二人的取法 以及此时取到第几张

由于最后要求二人数目一样

也就是要求二人数目差为0（划重点！！！）

所以我们将二人的取法根据二人数目差压缩为一个变量

由此可得：dp[i][j]表示取到第i张牌二人差为j时团队积分的最大值（1<=i<=n  -50000<=j<=50000)

dp[0][0]=0

2、如何解决y为负数的情况？

这里我们要用到一个技巧：状态偏移

所以我们可以用k+60000表示当j=k+10000的情况（多加一点避免出现其他状况）

由此可得：dp[i][j]表示取到第i张牌二人差为j-60000时团队积分的最大值（1<=i<=n  60000<=j<=120000)

dp[0][60000]=0

3、状态如何进行转移？

对于本题来讲 对于第i张牌存在3种状态：a取、b取、不取

但是这里要注意一点 并不是所有的dp[i][j]都是有效状态（不是所有到第i张牌的取法都能够找出差为j的方法）

如何处理这种状态？

首先我们将dp数组整体置为-1

由于不存在的状态一定不可能被其他方法取到（即dp[i][j]=-1)

而正常的dp[i][j]可以由max(dp[i-w[k][j]+c[k],dp[i][j-w[k]+c[k]）转移到

于是我们可以将两种状态统一起来

首先我们先将dp[i][j]由max(dp[i-w[k][j],dp[i][j-w[k])转移

不难推出如果dp[i][j]不为无效状态则dp[i][j]！=-1

如果dp[i][j]！=-1则dp[i][j]+=c[k]

同样的

dp[i][j]在保证第i张牌不取时可以由dp[i-1][j]转移

为了确保我们取到了最大的情况 可以对dp[i][j]和dp[i-1][j]的大小进行比较

如果dp[i-1][j]>dp[i][j] 就让dp[i][j]返回不取的情况（dp[i][j]=dp[i-1][j])

综上所述，我们得到的转移方程：

dp[i][j]=max(dp[i-1][j-x[i]],dp[i-1][j+x[i]])
   if(dp[i][j]!=-1)dp[i][j]+=y[i]
   if(dp[i][j]<dp[i-1][j])dp[i][j]=dp[i-1][j]

---

好了上代码吧

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[150][200050],x[150],y[150],n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
    memset(dp,-1,sizeof(dp));
    dp[0][100000]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=20000;j<=200005;j++)
        {
            dp[i][j]=max(dp[i-1][j-x[i]],dp[i-1][j+x[i]]);
            if(dp[i][j]!=-1)dp[i][j]+=y[i];
            if(dp[i][j]<dp[i-1][j])dp[i][j]=dp[i-1][j];
        }
    }
    printf("%d",dp[n][100000]);
    return 0;
}

本题是一道较为复杂的01背包问题，有必要将本题的想法、转移方程及表示彻底学会。