2018.8.17题解 2018暑假集训之纸牌

2018-08-17 09:37:18来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题面描述


 试题描述

小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背包问题,有必要将本题的想法、转移方程及表示彻底学会。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【共读Primer】23.&lt;4.3&gt; 逻辑和关系运算符 Page126

下一篇:vector