在通远的国家佛罗布尼亚，嫌犯是否有罪须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法:

控方和辩方会根据对候选人的喜欢程度给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的解方总分和控方总分之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。

输入数据:

输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意,1≤n≤200, 1≤m≤20,而且m≤n。接下来的n行，每行表示一个候选人的信息，它包含2个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔，最后一组数据n=m=0。

输出要求:

对每组数据:先输出一行，表示答案所属的组号， 如“lury #1”, “lury #2”，等。接下来的一行要象例子那样输出陪审团的控方总分和辨方总分。再下来一种要以长序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出出数据须以一个空行结束。

#include <cstdio>


#include <cstdlib>


#include <memory>


#include <algorithm>





int f[30][1000];


int Path[30][1000];


int P[300];


int D[300];


int Answer[30];





int main() {


    int i,j,k;


    int t1,t2;


    int n,m;


    int nMinP_D;


    int nCaseNo;


    nCaseNo=0;





    scanf("%d%d",&n,&m);


    while(n+m) {


        nCaseNo++;


        for(i=1; i<=n; i++)


            scanf("%d%d",&P[i],&D[i]);


        memset(f,-1,sizeof(f));


        memset(Path,0,sizeof(Path));


        nMinP_D=___(1)___;


        ___(2)___;


        for(j=0; j<m; j++) {


            for(k=0; ___(3)___; k++)


                if (___(4)___) {


                    for (i=1; i<=n; i++)


                        if (___(5)___) {


                            t1=j;


                            t2=k;


                            while(t1>0&&Path[t1][t2]!=j) {


                                t2-=P[Path[t1][t2]]-D[Path[t1][t2]];


                                t1--;


                            }


                            if (t1==0) {


                                f[j+1][k+P[i]-D[i]]=f[j][j]+P[i]+D[i];


                                Path[j+1][k+P[i]-D[i]]=i;


                            }


                        }


                }


        }


        i=nMinP_D;


        j=0;


        while (f[m][i+j]<0 && f[m][i-j]<0) j++;


        if(f[m][i+j]>f[m][i-j])


            k=i+j;


        else


            k=i-j;


        printf("Jury #%d\n", nCaseNo);


        printf("Best jury has value %d for prosccution and value %d for delencen:\n",(k-nMinP_D + f[m][k]) /2, (f[m][k]-k + nMinP_D) / 2);


        for(i=1; i<=m; i++) {


            ___(6)___;


            k =- P[Answer[i]] - D[Answer[i]];


        }        


        std::sort(Answer + 1, Answer + m + 1);


        for(i= 1; i<= m; i++) printf(" %d", Answer[i]);


        printf("\n");


        printf("\n");


        scanf("%d%d", &n, &m);


    }


    return 0;


}

选择题