POJ 2184 01背包+负数处理
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10200 | Accepted: 3977 |
Description
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.
Source
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
using namespace std; #define N 200005
#define sh 100000
#define inf 999999999 int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int abs(int x,int y){return x<?-x:x;} int dp[N]; struct node{
int v, w;
}a[]; int n; main()
{
int i, j, k;
while(scanf("%d",&n)==){
for(i=;i<n;i++) scanf("%d %d",&a[i].v,&a[i].w);
for(i=;i<N;i++) dp[i]=-inf;
dp[sh]=;
for(i=;i<n;i++){
if(a[i].v>){
for(k=N-;k>=a[i].v;k--) dp[k]=max(dp[k-a[i].v]+a[i].w,dp[k]);
}
else{
for(k=;k<N+a[i].v;k++) dp[k]=max(dp[k-a[i].v]+a[i].w,dp[k]);
}
}
int ans=;
for(i=sh;i<N;i++){
if(dp[i]>) {
ans=max(ans,i-sh+dp[i]);
} }
printf("%d\n",ans);
}
}
最新文章
- sharepoint powershell 批量处理匿名访问
- 排序算法练习--JAVA(插入、直接选择、冒泡、快速排序、非递归快速排序)
- win10系统iis下部署搭建https (ssl/tls)本地测试环境
- 我了个大擦-PDO(二)
- 浙江理工2015.12校赛-G Jug Hard
- document对象操作:浏览器页面文件
- NRF51822之GPIOTE介绍
- USACO Section 4.2: The Perfect Stall
- Hibernate逍遥游记-第5章映射一对多-01单向<;many-to-one>;、cascade=";save-update";、lazy、TransientObjectException
- shell脚本字符串截取
- PHP配置安全小技巧
- Linux(常用命令) 中常用的压缩丶解压缩格式命令和参数详解
- Oracle_where子句
- python中的进程池:multiprocessing.Pool()
- Mongodb Mysql NoSQL的区别和联系
- SYM File
- nodeppt:网页版 PPT
- hdoj-1114 (背包dp)
- Linq高级应用
- drupal7 判断用户是否具有某个权限
热门文章
- (一)keil4 MDK 开发环境下编写裸机程序 (参考杨铸 北航) (开发板只需要连接JLNK 就行了)
- C# 获取sql数据库表列名,及列名说明备注信息
- PHP排序函数
- 【final】站立会议---11.28
- 【转】PowerShell入门(二):PowerShell是Cmd命令行的加强版吗?
- .naturalWidth 和naturalHeight属性,
- 如何通过CRM评估客户价值和提高客户忠诚度?
- RSA算法基础详解
- (5) 深入理解Java Class文件格式(四)
- 16-underscore库(上)