POJ 2184 Cow Exhabition
fun..."
- Cows with Guns by Dana Lyons
The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by the cows. She has given each of the N (1 <= N <= 100) cows a thorough interview and determined two values for each cow: the smartness Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <= 1000) of the cow.
Bessie must choose which cows she wants to bring to her exhibition. She believes that the total smartness TS of the group is the sum of the Si's and, likewise, the total funness TF of the group is the sum of the Fi's. Bessie wants to maximize the sum of TS and TF, but she also wants both of these values to be non-negative (since she must also show that the cows are well-rounded; a negative TS or TF would ruin this). Help Bessie maximize the sum of TS and TF without letting either of these values become negative.
Input
* Lines 2..N+1: Two space-separated integers Si and Fi, respectively the smartness and funness for each cow.
Output
Sample Input
5
-5 7
8 -6
6 -3
2 1
-8 -5
Sample Output
8
Hint
Bessie chooses cows 1, 3, and 4, giving values of TS = -5+6+2 = 3 and TF
= 7-3+1 = 5, so 3+5 = 8. Note that adding cow 2 would improve the value
of TS+TF to 10, but the new value of TF would be negative, so it is not
allowed.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int inf = <<;
const int dir = ;
int dp[];
struct s{
int s, f;
}arr[]; int main(){
int n;
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d%d",&arr[i].s,&arr[i].f); for(int i=;i<=;i++)
dp[i] = -inf;
dp[] = ; for(int i=;i<n;i++){
if(arr[i].s < && arr[i].f < )
continue;
if(arr[i].s>){
for(int j=;j>=arr[i].s;j--){
if(dp[j-arr[i].s] > -inf){
dp[j] = max(dp[j],dp[j-arr[i].s]+arr[i].f);
}
} }else {// arr[i].s < 0 arr[i].f>=0
for(int j=arr[i].s;j<=+arr[i].s;j++){
if(dp[j-arr[i].s] > -inf){
dp[j] = max(dp[j],dp[j-arr[i].s]+arr[i].f);
}
}
}
}
int ans = ;
for(int i=;i<=;i++){
if(dp[i]>=)
ans = max(ans, dp[i]+i-);
}
printf("%d\n",ans);
return ;
}
对代码进行了优化。
首先是将dp从数组名变成了指针,令dp指向buf[100000]
这样、数组下标为负数时也不会越界。
优化关键在设置了两个变量,分别记录了有效区间的两个端点。
比如说 在处理第一个数的时候整个区间的都是无法达到的(除了原点)
而再像优化前的代码一样遍历一个200000的区间是无用的冗余。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int inf = <<;
int buf[];
int *const dp = buf + ; int main(){
int n, s, f;
scanf("%d",&n); for(int i=;i<=;i++)
buf[i] = -inf;
dp[] = ;// dp[0] == buf[100000] int l = , r = ;// 有效区间的左端点和右端点
for(int i=;i<n;i++){
scanf("%d%d",&s,&f);
if(s< && f <)//舍弃无用点
continue;
if(s > ){// 体积为正数 所以从大到小dp
for(int i=r;i>=l;i--)
dp[i+s] = max(dp[i+s],dp[i]+f);
}else {
for(int i=l;i<=r;i++)
dp[i+s] = max(dp[i+s],dp[i]+f);
}
if(s>)
r += s;
else
l += s;
}
int ans = ;
for(int i=;i<=r;i++){
if(dp[i] >= )
ans = max(ans, dp[i]+i);
}
printf("%d\n",ans);
return ;
}
最新文章
- c#smtp多线程
- Android工程师常见面试题集
- Linux学习笔记(3)-常用命令
- (转) 在C#用HttpWebRequest中发送GET/HTTP/HTTPS请求
- WindowsStore页面导航
- UVa 10048 Audiophobia【Floyd】
- [windows phone开发]新生助手的开发过程与体会三
- Unity3D 3D横版跑酷
- 如何在Dreamweaver中使用zen coding
- MEF初体验之十:部件重组
- Struts1、2种如何防止表单重复提交和两者的区别
- 开源自己写的一个拖拽库,兼容到IE8+
- 远程服务器数据交互技术:rsync,scp,mysqldump
- jQuery 中的简单动画
- Eigen::Matrix与array数据转换
- 访问权限,public private protected
- 茶馆小人书 (AFO)
- for循环输出数组中的分数
- 1、Dreamweaver+php开发网站第一步
- 基于Delphi的接口编程入门