HDU2955Robberies（DP）-白红宇

HDU2955Robberies（DP）

阅读量：6236 次

发布时间：2019-06-22

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

题目是说一小偷偷东西，第i个物品的价值是M[i]，被抓的概率是p[i]，现在要使得在被抓的概率在P以下时的所能偷得的最大价值。

不同于以往的01背包，这里需要将价值作为物品的大小。同时如果偷A被抓的概率是Pa，偷B被抓的概率是Pb那么偷两个物品被抓的概率就是

1-（1-Pa）*（1-Pb）

这时令DP[i][j]代表对于前i个物品偷得的价值为j时的最小的被抓的概率，这时可以得到状态转移方程：

DP[i][j] = MIN( DP[i-1][j], 1-(1-DP[i-1][j-M[i]])*(1-p[i]) )

最后的结果就是对于所有的DP[N][i]<P的最大的j

同样可以将状态压缩到一维的空间，注意边界（最初时）：

DP[i] = 1;一旦偷东西就会被抓

DP[0] = 0;什么都没偷一定不会被抓

1 #include  2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 using namespace std;15 #define INF 0x3f3f3f3f16 #define inf (-((LL)1<<40))17 #define lson k<<1, L, mid18 #define rson k<<1|1, mid+1, R19 #define mem0(a) memset(a,0,sizeof(a))20 #define mem1(a) memset(a,-1,sizeof(a))21 #define mem(a, b) memset(a, b, sizeof(a))22 #define FOPENIN(IN) freopen(IN, "r", stdin)23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)24 25 template
                  
                    T CMP_MIN(T a, T b) { return a < b; }26 template
                   
                     T CMP_MAX(T a, T b) { return a > b; }27 template
                    
                      T MAX(T a, T b) { return a > b ? a : b; }28 template
                     
                       T MIN(T a, T b) { return a < b ? a : b; }29 template
                      
                        T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }30 template
                       
                         T LCM(T a, T b) { return a / GCD(a,b) * b; }31 32 //typedef __int64 LL;33 //typedef long long LL;34 const int MAXN = 4000000+10;35 const int MAXM = 2000010;36 const double eps = 1e-1;37 38 double DP[11000], w[110], P;39 int c[110], N;40 41 int main()42 {43 int T;44 while(~scanf("%d%*c", &T)) while(T--)45 {46 mem1(DP);47 scanf("%lf%d", &P, &N);48 int S = 0;49 for(int i=0;i
                        
                         =0;i--) DP[i] = 1;55 DP[0] = 0;56 for(int i=0;i
                         
                          =c[i];j--)59 {60 DP[j] = MIN(DP[j], 1.0-(1-DP[j-c[i]])*(1-w[i]));61 }62 }63 int ans = 0;64 for(int i=0;i<=S;i++) if(DP[i] <= P) ans = i;65 printf("%d\n", ans);66 }67 return 0;68 }

转载于:https://www.cnblogs.com/gj-Acit/p/3719634.html

你可能感兴趣的文章