poj1015

题目意思：给定N对数，取期中的m对，要求取出sigma（a）与sigma(b)的差最小，如果有多种，输出两者和最大的一种。。。

DP求解.f[i,j,k]表示前i对数中选j对,第一个数之和减第二个数之和的差为k,这种情况下第二个数之和的最大值.

显然,f[i,j,k]=max(f[i-1,j,k],f[i-1,j-1,k-d[i]+d[i]]+p[i])；；

View Code

 1 /*
 2  State:Accept
 3  Time:2013.2.28
 4 */
 5 
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <fstream>
10 #include <algorithm>
11 #include <cstring>
12 #include <string>
13 #include <cmath>
14 #define minn -10000;
15 using namespace std;
16 int f[205][25][805] , finalx, finaly , n , m;
17 int result[25] , d[202], p[202] , ansx, ansy , ans ,test;
18 
19 void init(){
20        for (int i = 1; i <= n; ++i)
21           scanf("%d%d",&d[i],&p[i]);
22        memset(result, 0, sizeof(result));
23        memset(f , 0 ,sizeof(f));
24 }
25      
26 
27 void dp(){
28       int k2 ;
29       for (int i = 0; i <= n; ++i)
30          for (int j = 0; j <= m; ++j)
31              for (int k = 0; k <= 800; ++k)     
32                    if (j == 0 && k == 400)
33                    f[i][j][k] = 0;
34                       else f[i][j][k] =  minn;  
35       
36 
37       for (int i = 1; i <= n; ++i)
38          for (int j = 1; j <= min(m,i); ++j)
39              for (int k = 0; k <= 800; ++k){
40                   k2 = k - d[i] + p[i];   
41                   if (k2 < 0 || k2 > 800) continue;
42                   f[i][j][k] = max(f[i - 1][j - 1][k2] + d[i] + p[i] , f[i - 1][j][k]);
43              }
44       printf("Jury #%d\n", test);
45 }
46 
47 void find(int i , int j , int k){
48      if (k == 400 && j == 0) return;
49      if (f[i][j][k] == f[i-1][j][k]) find(i - 1, j ,k);
50      else {
51           result[j] = i;          
52           ansx += p[i];
53           ansy += d[i];
54           find(i - 1, j - 1 , k + p[i] - d[i]);
55 
56      }
57 }
58 
59 void printans(){
60      bool  bo = false;
61      int temp;
62      ans = minn;
63      ansx = ansy = 0;
64      for (int k = 0;  k <= 400; ++k) if (ans < 0)
65          for (int  i = 1; i <= n; ++i)
66            if (f[i][m][400 - k] >= 0 || f[i][m][400 + k] >= 0 ){
67                  temp = max(f[i][m][400 - k] , f[i][m][400 + k]);
68                  if (temp <= ans) continue;
69                  ans = temp;
70                  finalx = i;
71                  finaly = 400 + k;
72                  if (f[i][m][400 - k] > f[i][m][400 + k])
73                    finaly = 400 -k; 
74           }
75      find(finalx , m , finaly); 
76      printf("Best jury has value %d for prosecution and value %d for defence:\n",ansy, ansx);
77      for (int i = 1 ; i <= m; ++i)  
78                  printf("%d ",result[i]);
79      printf("\n\n");
80 }
81 
82 int main(){
83       freopen("poj1015.in","r",stdin);
84       freopen("poj1015.out","w",stdout);
85       scanf("%d%d",&n , &m);
86       while (n && m ){
87           ++ test;
88           init();
89           dp();
90           printans(); 
91           scanf("%d%d",&n , &m);
92           
93       }
94       fclose(stdin); 
95       fclose(stdout);
96 }

注意最后输出，有点麻换。。