POJ 1837 Balance(列挙状態の01バックパック)

1721 ワード

天秤があって、G個の異なる大きさの力を与えて、C個の天秤の両側の力の腕、すべての力を力の腕の上で置いた後に天秤の平衡の方案の数を求めます.私はこの問題から一般的なDPのような最適なサブ構造を見つけるのは難しいので、このような問題も私たちがすべての状況を「列挙」する必要があります.
一般に状態のDPを列挙する必要があり、bool f[i][j]はある状態が存在しないことを示すとする.この問題は案数を要求するので、f[i][j]が前のi種類の物品の平衡度をjと表す案数を設定する.そして負のバランスがあるので、私たちは彼を倍に拡大しました->15000.初期f[0][7500]=1(7500は平衡度0を表す)状態遷移方程式は、f[i][j]+=f[i-1][j-l[k]*w[i]]である.


#include 
 
   
    
  
#include 
  
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
            #include 
            
              #include 
             
               #include 
              
                #define MID(x,y) ((x+y)>>1) using namespace std; typedef long long LL; LL f[30][20000]; int l[30], w[30]; int main(){ int C, G; scanf("%d%d", &C, &G); for (int i = 0; i < C; i ++) scanf("%d", &l[i]); for (int i = 0; i < G; i ++) scanf("%d", &w[i]); for (int i = 0; i < 30; i ++) for (int j = 0; j < 20000; j ++) f[i][j] = 0; f[0][7500] = 1; for (int i = 1; i <= G; i ++){ for (int j = 0; j < 15000; j ++){ for (int k = 0; k < C; k ++) if (j - l[k]*w[i] >= 0) f[i][j] += f[i-1][j-l[k]*w[i-1]]; } } printf("%I64d
", f[G][7500]); return 0; }

PHP7.4でもマルチスレッド！！

JSON簡易応用