URAL 1244. Gentlemen （DP）

题意：给出一幅不完全的纸牌.算出哪些牌丢失了.

思路：算是背包一个吧。if f[j]>0 f[j+a[i]] += f[j];然后在记录一下路径。

 1 //1244
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <iostream>
 5 
 6 using namespace std ;
 7 
 8 int a[1100000] ,b[1010000];
 9 int dp[1010000] ;
10 
11 int main()
12 {
13     int w ;
14     while(~scanf("%d",&w))
15     {
16         int N ;
17         scanf("%d",&N) ;
18         for(int i = 1 ; i <= N ; i++)
19             scanf("%d",&a[i]) ;
20         memset(dp,0,sizeof(dp)) ;
21         memset(b,0,sizeof(b)) ;
22         dp[0] = 1 ;
23         for(int i = 1 ; i <= N ; i++)
24         {
25             for(int j = w ; j >= 0 ; j--)
26             {
27                 if(dp[j] > 0 && (j+a[i] <= w))
28                 {
29                     dp[j+a[i]] += dp[j] ;
30                     if(b[j+a[i]] <= 0)
31                         b[j+a[i]] = i;
32                 }
33             }
34         }
35         if(dp[w] == 0)
36             printf("0
") ;
37         else if(dp[w] > 1)
38             printf("-1
") ;
39         else
40         {
41             int c[110000] ;
42             memset(c,0,sizeof(c)) ;
43             for(int i = N ; i >= 1 ; i--)
44             {
45                 if(b[w] == i)
46                 {
47                     c[i] = true ;
48                     w -= a[i] ;
49                 }
50             }
51             for(int i = 1 ; i <= N; i++)
52                 if(c[i] == 0)
53                     printf("%d ",i) ;
54             printf("
") ;
55         }
56     }
57     return 0 ;
58 }

View Code