当前位置: 代码迷 >> 综合 >> #进阶:0816三部曲No.3终章:卡牌游戏
  详细解决方案

#进阶:0816三部曲No.3终章:卡牌游戏

热度:18   发布时间:2024-01-17 08:55:56.0

 

试题描述

小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。

 

数据范围虽然只有100,但是暴力搜索的话得搜2^100次(电脑会崩坏)。面对这种情况,seele只得选择最不擅长的DP...

细细研究,可以看出0-1背包的影子。但是他又和0-1背包有些不同...

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int x,card[100001],card2[100001],dp[101][120001],sum1=0,sum2=0;//定义卡牌正反面以及他们的差值,还有dp数组(别忘了定义全局变量!)
int main()
{cin>>x;for(int i=1;i<=x;i++){cin>>card[i]>>card2[i];sum1+=card[i];//记录一种选择情况的和}memset(dp,-1,sizeof(dp));//把dp赋值-1,假设现在没有发牌dp[0][60000]=0;//当后面的数=60000时,可以循环中保证数组不会越界。因为他们的差=0,所以这种方法成立,赋值0.for(int i=1;i<=x;i++){for(int j=60000-sum1;j<=60000+sum1;j++)//一个是最小值,一个是最大值{if(dp[i-1][j]!=-1)//不拿这张牌的情况{dp[i][j]=max(dp[i-1][j],dp[i][j]);//查找使公共和最大的情况}if(dp[i-1][j+card[i]]!=-1)//小A取走这张牌{dp[i][j]=max(dp[i-1][j+card[i]]+card2[i],dp[i][j]);//用max函数查找}if(dp[i-1][j-card[i]]!=-1)//小B取走这张牌{dp[i][j]=max(dp[i][j],dp[i-1][j-card[i]]+card2[i]);//三种情况都要算上啊~}}}cout<<dp[x][60000];//输出最终的总和
}

记住DP方程

感谢LJQMIAO_的大力支持!(Seele的原创)