POJ 2184 Cow Exhibition （dp 转换01背包）-白红宇

POJ 2184 Cow Exhibition （dp 转换01背包）

阅读量：4072 次

发布时间：2019-05-25

本文共 1004 字，大约阅读时间需要 3 分钟。

题目：

题目大意：

有N个物品，每个物品有属性Si和Fi，-1000 <= Si, Fi <= 1000, 每种物品最多只能选一次，问怎样选使得物品的所有Si和Fi属性之和最大，并且要求Si之和与Fi之和都不能下于0.

思路：

这题想了很久都没思路，于是跟前辈请教了下，恍然大悟。把属性Si当做是物品的费用，Fi当做是价值，然后做01背包即可。

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #define MP make_pair#define SQ(x) ((x)*(x))typedef long long int64;const double PI = acos(-1.0);const int INF = 0x3f3f3f3f;using namespace std;const int MOD = 1000000007;const int MAXN = 110;const int ADD = 1000*100;int n, m;int S[MAXN], F[MAXN];int f[1000000];int main(){ scanf("%d", &n); int sum = 0; int idx = 0; for(int i=0; i
            
             0) sum += S[idx]; ++idx; } memset(f, -INF, sizeof(f)); f[ADD] = 0; for(int i=0; i
             
              0){ for(int v=sum+ADD; v>=S[i]; --v){ f[v] = max(f[v], f[v-S[i]]+F[i]); } }else{ for(int v=0; v-S[i]<=sum+ADD; ++v){ f[v] = max(f[v], f[v-S[i]]+F[i]); } } } int ans = 0; for(int i=0; i<=sum; ++i)if(f[i+ADD]>=0) ans = max(i+f[i+ADD], ans); printf("%d\n", ans); return 0;}

转载地址：http://kvzni.baihongyu.com/

你可能感兴趣的文章