Cow Exhibition POJ - 2184
2024-08-27 19:54:20
题目地址:https://vjudge.net/problem/POJ-2184
下面的解释是从一个大佬那搬来的,讲的很清楚
题意:给定一些奶牛,每个牛有s和f两个属性值,有正有负,要求选出一些牛,
使得这些牛的两种属性的和的加和最大,且这些牛的两种属性分别求加和不能为负。
分析:dp,开始想到dp[i][s][f],表示前i头牛能否实现属性和分别为s, f。空间和时间都不允许,
要将f从状态中拿出來,让f的属性和作为所求的值。即变为d[i][s] = f的形式。
表示用前i头牛构成s属性和为s的情况下f属性和最大为多少。状态转移从两种情况来,即用或者不用当前的牛。
dp[i][j] = max(dp[i - 1][j - s[i]] + f[i], dp[i - 1][j])。在实际操作的时候可以将第一维去掉,进行空间上的优化。
但是由于s[i]的值有正有负,所以在填写数组的顺序要根据s[i]的值来决定,
若为正则从右到左(类似01背包的空间优化),若为负则从左到右。
注意:动态规划中状态维和值是可以相互转化的。状态维过多,效率低的时候,
可以把将其转化为数组值;同理,数组值不唯一无法规划时,可以增加状态维使状态更详细
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define mv (int)1e5
#define N 105
#define inf (1LL << 30) - 1
#define maxn (int)2e5 + 10 int dp[maxn];
int s[N], f[N];
int n; void input(){ rep(i, , maxn - ) dp[i] = -inf; cin >> n;
rep(i, , n) cin >> s[i] >> f[i];
} void work(){ dp[ + mv] = ; rep(i, , n){
if (s[i] > ){
per(o, (int)1e5, (int)(-1e5 + s[i]))
dp[o + mv] = max(dp[o + mv], dp[o - s[i] + mv] + f[i]);
}
else{
rep(o, (int)-1e5, (int)(1e5 + s[i]))
dp[o + mv] = max(dp[o + mv], dp[o - s[i] + mv] + f[i]);
}
} int ans = ;
rep(i, , (int)1e5){
if (dp[i + mv] >= ) ans = max(ans, i + dp[i + mv]);
} cout << ans << endl;
} int main(){ ios::sync_with_stdio(false);
cin.tie();
input();
work(); return ;
}
最新文章
- PHP5.5.13 + Apache2.4.7安装配置流程详解
- OpenGL图元的颜色属性
- arcgis server账号需要设置地图缓存的访问权限
- codevs 1204 寻找子串位置
- HDU 5675 ztr loves math
- JS思维导图
- jquery easy ui 学习 (8)basic treegrid
- Liferay 6.1开发学习
- Spring Boot 配置优先级顺序
- 微信支付错误两个问题的解决:curl出错,错误码:60
- hdu_1254_推箱子(双BFS)
- jquery选择器 之 获取父级元素、同级元素、子元素(转)
- Java各种工具下载
- Python进阶---面向对象的程序设计思想
- C# RichTextBox设置行间距
- C# 入门经典
- 【python进阶】深入理解系统进程1
- layer.js 中弹框显示不全的问题
- jar导入本地maven库
- [AngularJS] “多重路由”嵌套模块——AngularJS“路由”嵌套学习资料教程
热门文章
- ios7 获取UITablleViewCell
- WPF控件的一些特殊应用
- Java Class SecurityManager
- C# WebApi使用AttributeRoutes特性路由
- WPF 创建无边框的圆角窗口
- dataGrid 源更新 事件
- API HOOK介绍 【转】
- 修复VirtualBox ";This kernel requires the following features not present on the CPU: pae Unable to boot – please use a kernel appropriate for your CPU";(安装深度Linux的时候就需要)
- 百度网盘web端项目总结
- Windows RabbitMQ 安装