01背包(类) UVA 10564 Paths through the Hourglass-白红宇

01背包(类) UVA 10564 Paths through the Hourglass

阅读量：6478 次

发布时间：2019-06-23

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

1 /*  2     01背包(类)：dp[i][j][k] 表示从(i, j)出发的和为k的方案数，那么cnt = sum (dp[1][i][s])  3             状态转移方程：dp[i][j][k] = dp[i+1][j][k-c] + dp[i+1][j+1][k-c];(下半部分)    上半部分类似  4             因为要输出字典序最小的，打印路径时先考虑L     5 */  6 /************************************************  7  * Author        :Running_Time  8  * Created Time  :2015-8-9 15:45:11  9  * File Name     :UVA_10564.cpp 10  ************************************************/ 11  12 #include 
     
       13 #include 
      
        14 #include 
       
         15 #include 
        
          16 #include 
         
           17 #include 
          
            18 #include 
           
             19 #include 
            
              20 #include 
             
               21 #include 
              
                22 #include 
               
                 23 #include 
                
                  24 #include 
                  25 #include 
                  
                    26 #include 
                   
                     27 #include 
                    
                      28 #include 
                     
                       29 using namespace std; 30 31 #define lson l, mid, rt << 1 32 #define rson mid + 1, r, rt << 1 | 1 33 typedef long long ll; 34 const int MAXN = 22; 35 const int MAXS = 5e2 + 10; 36 const int INF = 0x3f3f3f3f; 37 const int MOD = 1e9 + 7; 38 int a[MAXN*2][MAXN]; 39 ll dp[MAXN*2][MAXN][MAXS]; 40 int n, s; 41 42 void print(int x, int y, int sum) { 43 if (x >= 2 * n - 1) return ; 44 int v = a[x][y]; 45 if (x < n) { 46 if (y > 1 && dp[x+1][y-1][sum-v]) { 47 printf ("L"); print (x+1, y-1, sum - v); 48 } 49 else { 50 printf ("R"); print (x+1, y, sum - v); 51 } 52 } 53 else { 54 if (dp[x+1][y][sum-v]) { 55 printf ("L"); print (x+1, y, sum - v); 56 } 57 else { 58 printf ("R"); print (x+1, y+1, sum - v); 59 } 60 } 61 } 62 63 int main(void) { //UVA 10564 Paths through the Hourglass 64 while (scanf ("%d%d", &n, &s) == 2) { 65 if (!n && !s) break; 66 for (int i=1; i<=n; ++i) { 67 for (int j=1; j<=n-i+1; ++j) scanf ("%d", &a[i][j]); 68 } 69 for (int i=n+1; i<=2*n-1; ++i) { 70 for (int j=1; j<=i-n+1; ++j) scanf ("%d", &a[i][j]); 71 } 72 73 memset (dp, 0, sizeof (dp)); 74 for (int i=1; i<=n; ++i) { 75 int c = a[2*n-1][i]; 76 dp[2*n-1][i][c] = 1; 77 } 78 for (int i=2*n-2; i>=n; --i) { 79 for (int j=1; j<=i-n+1; ++j) { 80 int c = a[i][j]; 81 for (int k=c; k<=s; ++k) { 82 dp[i][j][k] = dp[i+1][j][k-c] + dp[i+1][j+1][k-c]; 83 } 84 } 85 } 86 ll cnt = 0; 87 for (int i=n-1; i>=1; --i) { 88 for (int j=1; j<=n-i+1; ++j) { 89 int c = a[i][j]; 90 for (int k=c; k<=s; ++k) { 91 if (j > 1) dp[i][j][k] += dp[i+1][j-1][k-c]; 92 if (j < n - i + 1) dp[i][j][k] += dp[i+1][j][k-c]; 93 } 94 if (i == 1) cnt += dp[i][j][s]; 95 } 96 } 97 printf ("%lld\n", cnt); 98 for (int i=1; i<=n; ++i) { 99 if (dp[1][i][s]) {100 printf ("%d ", i-1);101 print (1, i, s); break;102 }103 }104 puts ("");105 }106 107 return 0;108 }