1 /* 2     题意：给出少了若干卡片后的总和，和原来所有卡片，问少了哪几张 3     DP：转化为少了的总和是否能有若干张卡片相加得到，dp[j+a[i]] += dp[j]; 4         记录一次路径，当第一次更新的时候 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 #include 
          
           12 #include 
           
            13 using namespace std;14 15 const int MAXN = 1e5 + 10;16 const int INF = 0x3f3f3f3f;17 int a[MAXN];18 int dp[MAXN];19 int rt[MAXN];20 21 int main(void) //URAL 1244 Gentlemen22 {23 //freopen ("U.in", "r", stdin);24 25 int tot, n;26 while (scanf ("%d", &tot) == 1)27 {28 scanf ("%d", &n);29 int sum = 0;30 for (int i=1; i<=n; ++i) {scanf ("%d", &a[i]); sum += a[i];}31 if (tot > sum) {puts ("0"); continue;}32 33 memset (rt, 0, sizeof (rt));34 memset (dp, 0, sizeof (dp));35 sum -= tot;36 dp[0] = 1;37 for (int i=1; i<=n; ++i)38 {39 for (int j=sum-a[i]; j>=0; --j)40 {41 if (dp[j] && dp[j+a[i]] == 0)42 {43 rt[j+a[i]] = i;44 }45 dp[j+a[i]] += dp[j];46 }47 }48 49 if (dp[sum] == 0) {puts ("0"); continue;}50 else if (dp[sum] == 1)51 {52 vector
            
              ans;53 for (int i=n; i>=1; --i)54 {55 if (rt[sum] == i) {ans.push_back (i); sum -= a[i];}56 }57 for (int i=ans.size ()-1; i>=0; --i) printf ("%d%c", ans[i], (i==0) ? '\n' : ' ');58 }59 else puts ("-1");60 }61 62 return 0;63 }