ZOJ 3905 Cake
Cake
Time Limit: 4 Seconds Memory Limit: 65536 KB
Alice and Bob like eating cake very much. One day, Alice and Bob went to a bakery and bought many cakes.
Now we know that they have bought n cakes in the bakery. Both of them like delicious cakes, but they evaluate the cakes as different values. So they decided to divide those cakes by following method.
Alice and Bob do n / 2 steps, at each step, Alice choose 2 cakes, and Bob takes the cake that he evaluates it greater, and Alice take the rest cake.
Now Alice want to know the maximum sum of the value that she can get.
Input
The first line is an integer T which is the number of test cases.
For each test case, the first line is an integer n (1<=n<=800). Note that n is always an even integer.
In following n lines, each line contains two integers a[i] and b[i], where a[i] is the value of ith cake that Alice evaluates, and b[i] is the value of ith cake that Bob evaluates. (1<=a[i], b[i]<=1000000)
Note that a[1], a[2]..., a[n] are n distinct integers and b[1], b[2]..., b[n] are n distinct integers.
Output
For each test case, you need to output the maximum sum of the value that Alice can get in a line.
Sample Input
1
6
1 6
7 10
6 11
12 18
15 5
2 14
Sample Output
28
Author: HUA, Yiwei
解题:$动态规划,dp[i][j]表示有i个cake,选了j个给Bob,剩下的给Alice,由于预先按每块cake的b属性由高到低排序$
$所以,可以保证每次加入的Cake 如果是给Alice的一定可以成功的给Alice,因i里面有j个的cake的b属性比当前cake的b属性大$
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
typedef long long LL;
struct Cake{
int a,b;
bool operator<(const Cake &rhs)const{
return b > rhs.b;
}
}cake[maxn];
LL dp[][maxn]; int main(){
int kase,n;
scanf("%d",&kase);
while(kase--){
scanf("%d",&n);
for(int i = ; i <= n; ++i)
scanf("%d%d",&cake[i].a,&cake[i].b);
sort(cake + ,cake + n + );
memset(dp,,sizeof dp);
int cur = ;
for(int i = ; i <= n; ++i){
for(int j = ((i-)>>); j >= ; --j){
dp[cur^][i-j] = max(dp[cur^][i-j],dp[cur][i--j]);
dp[cur^][i-j-] = max(dp[cur^][i-j-],dp[cur][i--j] + cake[i].a);
}
memset(dp[cur],,sizeof dp[cur]);
cur ^= ;
}
printf("%lld\n",dp[cur][n>>]);
}
return ;
}
最新文章
- Maven仓库搭建--nexus私服
- linux网络环境下socket套接字编程(UDP文件传输)
- *[hackerrank]Girlfriend &; Necklace
- Ubuntu 14.04 &; ant: Unable to locate tools.jar. Expected to find it in /usr/lib/jvm/java-7-openjdk-i386/lib/tools.jar
- java中的“包”与C#中的“命名空间
- Java学习笔记--StringTokenizer的使用
- Analysis about different methods for reading and writing file in Java language
- JAVA连接数据库后,对数据库进行增删改查
- DevOps之网络
- [BZOJ]1050 旅行comf(HAOI2006)
- 微信小程序开发---视图层(View)
- spark-2.4.0-hadoop2.7-简单操作
- BFS总结
- c/c++连通图的遍历(深度遍历/广度遍历)
- delphi java 日期 转换 获取Unix时间戳
- cakephp 如何在一个模型里调用另一个模型
- 浅谈 JSON 那些被转义的字符们
- 从头认识多线程-1.9 迫使线程停止的方法-return法
- jQuery开发者眼中的AngularJS
- 用Apache Spark和TensorFlow进行的深度学习