Cow Exhibition POJ - 2184

发布时间：2020-12-14 04:41:56 所属栏目：大数据来源：网络整理

导读：题目地址：https://vjudge.net/problem/POJ-2184 下面的解释是从一个大佬那搬来的，讲的很清楚题意：给定一些奶牛，每个牛有s和f两个属性值，有正有负，要求选出一些牛，使得这些牛的两种属性的和的加和最大，且这些牛的两种属性分别求加和不能为负。分析

题目地址：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背包的空间优化），若为负则从左到右。
注意：动态规划中状态维和值是可以相互转化的。状态维过多，效率低的时候，
可以把将其转化为数组值；同理，数组值不唯一无法规划时，可以增加状态维使状态更详细

 1 #include<iostream>

 2 #include<algorithm>
 3 using namespace std;  4 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
 5 #define per(i,k) for(int i = (j); i >= (k); i--)
 6 #define mv (int)1e5
 7 #define N 105
 8 #define inf (1LL << 30) - 1
 9 #define maxn (int)2e5 + 10
10 
11 int dp[maxn]; 12 int s[N],f[N]; 13 int n; 14 
15 void input(){ 16 
17     rep(i,0,maxn - 1) dp[i] = -inf; 18 
19     cin >> n; 20     rep(i,1,n) cin >> s[i] >> f[i]; 21 } 22 
23 void work(){ 24 
25     dp[0 + mv] = 0; 26 
27     rep(i,1,n){ 28         if (s[i] > 0){ 29             per(o,(int)1e5,(int)(-1e5 + s[i])) 30                 dp[o + mv] = max(dp[o + mv],dp[o - s[i] + mv] + f[i]); 31  } 32         else{ 33             rep(o,(int)-1e5,(int)(1e5 + s[i])) 34                 dp[o + mv] = max(dp[o + mv],dp[o - s[i] + mv] + f[i]); 35  } 36  } 37 
38     int ans = 0; 39     rep(i,(int)1e5){ 40         if (dp[i + mv] >= 0) ans = max(ans,i + dp[i + mv]); 41  } 42 
43     cout << ans << endl; 44 } 45 
46 int main(){ 47 
48     ios::sync_with_stdio(false); 49     cin.tie(0); 50  input(); 51  work(); 52 
53     return 0; 54 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!