DP URAL 1244 Gentlemen

题目传送门

 /*
     题意：已知丢失若干卡片后剩余的总体积，并知道原来所有卡片的各自的体积，问丢失的卡片的id
     DP递推：首先从丢失的卡片的总体积考虑，dp[i] 代表体积为i的方案数，从dp[0] = 1递推，累加的条件是dp[j]上一个状态已经有方案，
             若dp[w] > 1表示有多种方案，外加p[j+a[i]] = i的记录路径数组
     我开始用了暴力DFS超时，dp不会写，看了题解发现是个递推，有点像01背包的题目:)
     详细解释：http://blog.****.net/neko01/article/details/10033787
 */
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 #include <cstring>
 #include <string>
 #include <cmath>
 using namespace std;

 const int MAXN = 1e2 + ;
 const int MAXM = 1e6 + ;
 const int INF = 0x3f3f3f3f;
 int a[MAXN];
 int p[MAXM];
 int ans[MAXN];
 int dp[MAXM];

 int main(void)        //URAL 1244 Gentlemen
 {
     //freopen ("L.in", "r", stdin);

     int w, n, sum;
     while (scanf ("%d", &w) == )
     {
         sum = ;
         scanf ("%d", &n);
         for (int i=; i<=n; ++i)
         {
             scanf ("%d", &a[i]);    sum += a[i];
         }

         memset (p, , sizeof (p));
         memset (dp, , sizeof (dp));
         dp[] = ;    w = sum - w;

         for (int i=; i<=n; ++i)
         {
             for (int j=w-a[i]; j>=; --j)
             {
                 if (dp[j])
                 {
                     if (!dp[j+a[i]])    p[j+a[i]] = i;
                     dp[j+a[i]] += dp[j];
                 }
             }
         }

         int cnt = ;
         if (dp[w] == )    puts ("");
         else if (dp[w] == )
         {
             for (int i=n; i>=; --i)
             {
                 if (p[w] == i)
                 {
                     ans[++cnt] = i;
                     w -= a[i];
                 }
             }

             for (int i=cnt; i>=; --i)
             {
                 printf ("%d%c", ans[i], (i==) ? '\n' : ' ');
             }
         }
         else    puts ("-1");
     }

     return ;
 }