card

2018/08/16 19:35
阅读数 31
 

【问题描述】

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

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

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

【输入】

第一行n

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

【输出】

一行一个整数

表示小a的积分和小b的积分相等的时候,团队积分的最大值。

【输入输出样例】

card.in

card.out

4

3 1

2 2

1 4

1 4

10

数据范围

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

问题分(闲)析(聊):这道题是本蒟蒻上午考试的一道题,上午怎么想也想不出来。下午老师一讲思路就明白了,然后调题的时候一直在WA,刚写出来(在家,学校的内网登不上。还没测评,但应该是对了)。

 思路:这道题是一道动态规划,一张牌有三种情况,给A,给B,和谁都不给。怎么判断一样多呢?算一下数据范围,定个中点这道题的数据是100000,那就定55000,多开点(当然dp数组就要开110000了)。参考代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int dp[105][110005],n,x[105],s[100005],y[105];
 4 int main()
 5 {
 6     //freopen("card.in","r",stdin);
 7     //freopen("card.out","w",stdout);
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;i++)
10     {
11         scanf("%d%d",&x[i],&y[i]);//输入个人值和团队值  
12     }
13     memset(dp,-1,sizeof(dp));// 都赋成-1,即没有意义的待转移状态 
14     dp[0][55000]=0;//第零张牌,双方平衡,团队值也是零 
15     for(int i=1;i<=n;i++)//第几张牌 
16     {
17         for(int j=6000;j<=110000;j++)
18         {
19             for(int k=-1;k<=1;k++)//枚举三种状态,-1(给A),0(谁都不给),1(给B) 
20             {
21                 if(k!=0&&dp[i-1][j+k*x[i]]!=-1)//这个待转移状态有意义吗 
22                 {
23                     dp[i][j]=max((dp[i-1][j+k*x[i]]+y[i]),dp[i][j]);//要求出最大值 
24                 }
25                 else if(k==0&&dp[i-1][j]!=-1) dp[i][j]=max(dp[i-1][j],dp[i][j]);//同上 
26             }
27         }
28     }
29     printf("%d",dp[n][55000]);//输出发完n张牌后双方个人值相等的团队最大值 
30     return 0;//完美结束 
31 }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部