Jury Compromise POJ 1015(dp)

原题

题目链接

题目分析

有点难的dp,首先可以这样定义dp[j][k],选了j个人,它们的p[i]-d[i]的和为k,此时的最大p[i]+d[i]的值,由于p[i]-d[i]的值可能为负,所以必须处理一下,也就是让k的值加上m*20(也就是设k=m*20为0),就可以保证k的值为非负整数.这个dp初始化为-1,就是当选j个人,它们的p[i]-d[i]无法凑成k时,dp[j][k]的值为-1,更新方式为,如果dp[j][k]!=-1,就从n个人中挑dp[j+1][k+p[i]-d[i]]<dp[j][k]+p[i]+d[i]的人去更新dp[j+1][k+p[i]-d[i]],而且这个人不能在dp[j][k]中被选过.而为了检查dp[j][k]有没有选过第i个人,可以构建一个标记数组,path[j][k]表示最后一个人选的是i,这样就往下找直到j为0就可以判定i在dp[j][k]有没有被选过了.更新完dp后按定义就可以从m*20开始在附近搜索答案了,找到答案后根据标记数组也可以找到这个方案选了谁.

代码

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <utility>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <cstring>
 7 #include <string>
 8 #include <vector>
 9 #include <stack>
10 #include <queue>
11 #include <map>
12 #include <set> 
13 
14 using namespace std;
15 typedef long long LL;
16 const int INF_INT=0x3f3f3f3f;
17 const LL INF_LL=0x3f3f3f3f3f3f3f3f; 
18 
19 int n,m;
20 int dp[30][1000];
21 int p[300],d[300];
22 int path[30][1000];
23 int ans[30];
24 
25 int main()
26 {
27 //    freoGen("black.in","r",stdin);
28 //    freopen("black.out","w",stdout);
29     int cnt=1;
30     while(cin>>n>>m&&(n||m))
31     {
32         
33         for(int i=1;i<=n;i++) cin>>p[i]>>d[i];
34     
35         for(int j=0;j<=m;j++)
36         for(int k=0;k<=40*m;k++)
37         dp[j][k]=-1,path[j][k]=0;
38     
39         dp[0][20*m]=0;
40         for(int j=0;j<m;j++)
41         for(int k=0;k<=40*m;k++)
42         {
43             
44             if(dp[j][k]!=-1)
45             {
46                 for(int i=1;i<=n;i++)
47                 {
48                     int sum=k+p[i]-d[i];
49                     if(sum>=0&&sum<=40*m)
50                     {
51                         if(dp[j+1][sum]<dp[j][k]+d[i]+p[i])
52                         {
53                             int t1=j,t2=k;
54                             while(path[t1][t2]!=i&&t1>0)
55                             {
56                                 t2=t2-p[path[t1][t2]]+d[path[t1][t2]];
57                                 t1--;
58                             }
59                             if(!t1)
60                             {
61                                 dp[j+1][sum]=dp[j][k]+d[i]+p[i];
62                                 path[j+1][sum]=i;
63                             }
64                         }
65                     }
66                 }
67             }
68         }
69     
70         int res,t=0;
71         while(dp[m][20*m+t]==-1&&dp[m][20*m-t]==-1) t++;
72         if(dp[m][20*m+t]>dp[m][20*m-t]) res=20*m+t;
73         else res=20*m-t;
74     //    printf("res=%d,t=%d,dp=%d\n",res,t,dp[m][res]);
75     /*    for(int j=0;j<=m;j++)
76         for(int k=0;k<=40*m;k++)
77         if(dp[j][k]!=-1) printf("dp %d %d = %d\n",j,k-20*m,dp[j][k]);
78         printf("\n\n");
79         for(int j=0;j<=m;j++)
80         for(int k=0;k<=40*m;k++)
81         if(path[j][k]) printf("path %d %d = %d\n",j,k-20*m,path[j][k]);    
82     */    
83         int x=(res-20*m+dp[m][res])/2,y=dp[m][res]-x;
84         printf("Jury #%d\n",cnt++);
85         printf("Best jury has value %d for prosecution and value %d for defence:\n",x,y);
86         t=0;
87         for(int j=m;j>0;j--)
88         {
89             ans[t++]=path[j][res];
90             res-=p[path[j][res]]-d[path[j][res]];
91         }
92         sort(ans,ans+m);
93         for(int j=0;j<m;j++) printf(" %d",ans[j]);
94         printf("\n\n");
95     }
96     return 0;
97 }