2018.8.17题解 2018暑假集训之纸牌
2018-08-17 09:37:18来源:博客园 阅读 ()
题面描述
试题描述
小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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- GPLT-天梯赛-题解目录 2020-03-22
- 题解 P5116 【[USACO18DEC]Mixing Milk】 2020-03-14
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash