POJ 1051 Jury Compromise —

POJ 1051 Jury Compromise ——（暴力DP）

　　题目不难，暴力地dp一下就好，但是不知道我WA在哪里了，对拍了好多的数据都没找出错误= =。估计又是哪里小细节写错了QAQ。。思路是用dp[i][j]表示已经选了i个，差值为j的最大和。转移的话暴力枚举当前选那个即可。代码如下（WA的，以后有机会再找找错在哪里吧0.0）：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <set>
 5 using namespace std;
 6 const int N = 200 + 5;
 7 
 8 int n,m;
 9 int a[N],b[N];
10 struct node
11 {
12     int now,pre,val;
13     int a,b;
14 }dp[20+5][800+5];
15 
16 set<int> get(int x)
17 {
18     set<int> S;
19     for(int i=m;i>=1;i--)
20     {
21         S.insert(dp[i][x].now);
22         x = dp[i][x].pre;
23     }
24     return S;
25 }
26 
27 int main()
28 {
29     int kase = 1;
30     while(scanf("%d%d",&n,&m) == 2)
31     {
32         if(n == 0 & m == 0) break;
33         for(int i=1;i<=n;i++) scanf("%d%d",a+i,b+i);
34         for(int i=0;i<=800;i++) dp[0][i] = (node){-1,-1,0,0,0};
35         dp[0][400] = (node){0,-1,0,0,0};
36         for(int i=1;i<=m;i++)
37         {
38             for(int j=0;j<=800;j++)
39             {
40                 dp[i][j] = (node){-1,-1,0,0,0};
41                 for(int k=1;k<=n;k++)
42                 {
43                     int add = a[k] - b[k];
44                     if(j-add < 0 || j - add > 800) continue;
45                     int pre = j - add;
46                     if(dp[i-1][pre].now == -1) continue;
47                     int flag = 1;
48                     for(int p=i-1;p>=1;p--)
49                     {
50                         if(dp[p][pre].now == k)
51                         {
52                             flag = 0;
53                             break;
54                         }
55                         else pre = dp[p][pre].pre;
56                     }
57                     if(flag == 0) continue;
58                     if(dp[i-1][j - add].val + a[k]+b[k] > dp[i][j].val)
59                     {
60                         dp[i][j] = (node){k,j-add,dp[i-1][j - add].val + a[k]+b[k],
61                         dp[i-1][j - add].a + a[k], dp[i-1][j - add].b + b[k]};
62                     }
63                 }
64             }
65         }
66         set<int> S;
67         int aa, bb;
68         for(int add=0;add<=400;add++)
69         {
70             if(dp[m][400-add].now == -1 && dp[m][400+add].now == -1) continue;
71             int temp = 0;
72             if(dp[m][400-add].now != -1)
73             {
74                 temp = dp[m][400-add].val;
75                 S = get(400-add);
76                 aa = dp[m][400-add].a, bb = dp[m][400-add].b;
77             }
78             if(dp[m][400+add].now != -1)
79             {
80                 if(dp[m][400+add].val > temp)
81                 {
82                     S = get(400+add);
83                     aa = dp[m][400+add].a, bb = dp[m][400+add].b;
84                 }
85             }
86             break;
87         }
88         printf("Jury #%d
",kase++);
89         printf("Best jury has value %d for prosecution and value %d for defence:
",aa,bb);
90         for(set<int>::iterator it=S.begin();it!=S.end();it++) printf(" %d",*it);
91         puts("
");
92     }
93     return 0;
94 }