URAL 1244. Gentlemen(DP)

这题不难啊。。。标记一下就行了。表示啥想法也没有。
 1 #include <cstring>
 2 #include <cstdio>
 3 #include <string>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <map>
 8 using namespace std;
 9 #define INF 100000000
10 int dp[100001];
11 int flag[100001];
12 int p[101];
13 int o[101];
14 int que[101];
15 int pre[100001];
16 int main()
17 {
18     int i,j,n,m;
19     scanf("%d%d",&m,&n);
20     for(i = 1; i <= n; i ++)
21         scanf("%d",&p[i]);
22     for(i = 1; i <= m; i ++)
23         dp[i] = INF;
24     flag[0] = 1;
25     for(i = 1; i <= n; i ++)
26     {
27         for(j = m; j >= p[i]; j --)
28         {
29             if(dp[j] > dp[j-p[i]] + p[i])
30             {
31                 dp[j] = dp[j-p[i]] + p[i];
32                 pre[j] = i;
33             }
34             if(dp[j] == dp[j-p[i]] + p[i])
35             {
36                 flag[j] += flag[j-p[i]];
37             }
38         }
39     }
40     if(dp[m] != m)
41         printf("0
");
42     else if(flag[m] > 1)
43         printf("-1
");
44     else
45     {
46         while(m)
47         {
48             o[pre[m]] = 1;
49             m -= p[pre[m]];
50         }
51         int z = 1;
52         for(i = 1; i <= n; i ++)
53         {
54             if(!o[i])
55             {
56                 if(z)
57                 {
58                     printf("%d",i);
59                     z = 0;
60                 }
61                 else
62                     printf(" %d",i);
63             }
64         }
65     }
66     return 0;
67 }