#include <iostream>
#include <cstdio>
#define maxn 210
using namespace std;
bool F[maxn][22][805];
int N[maxn][22][805];
int a[maxn],b[maxn];
int di[maxn];
int Ans[22];
int main()
{
    int candidate,juryNumber;
    int test=0;
    while(scanf("%d%d",&candidate,&juryNumber),candidate)
    {
        for(int i=0;i<candidate;i++)
        {
            scanf("%d%d",a+i+1,b+i+1);
            di[i+1]=b[i+1]+20-a[i+1];
        }
        memset(F,0,sizeof(F));
        memset(N,0,sizeof(N));
        for(int i=0;i<=candidate;i++)
            for(int j=0;j<=juryNumber;j++)
                F[i][j][0]=1;
        for(int i=1;i<=candidate;i++)
        {
            for(int j=1;j<=juryNumber;j++)
            {
                if(j>i)
                    break;
                for(int d=0;d<=40*juryNumber;d++)
                {
                    if(d>=di[i])
                    if(F[i-1][j-1][d-di[i]])
                    {
                        F[i][j][d]=1;
                        N[i][j][d]=N[i-1][j-1][d-di[i]]+a[i];
                    }
                    if(F[i-1][j][d])
                    {
                        F[i][j][d]=1;
                        N[i][j][d]=max(N[i][j][d],N[i-1][j][d]);
                    }
                }
            }
        }
        int ans=999999999;
        for(int i=juryNumber*20;i<=40*juryNumber;i++)
            if(F[candidate][juryNumber][i])
                {
                    ans=i;
                    break;
                }
        
        for(int i=juryNumber*20;i>=0;i--)
            if(F[candidate][juryNumber][i])
            {
                ans=((juryNumber-i<ans-juryNumber)?i:ans);
                break;
            }
        
        test++;
        printf("Jury #%d\n",test);
        printf("Best jury has value %d ",N[candidate][juryNumber][ans]);
        printf("for prosecution and value %d ",N[candidate][juryNumber][ans]+ans-juryNumber*20);
        printf("for defence: \n");
        int i=candidate,j=juryNumber;
        while(j)
        {
            if(N[i][j][ans]==N[i-1][j][ans])
                i--;
            else
            {
                Ans[j]=i;
                ans-=di[i];
                i--;
                j--;
            }
        }
        printf(" ");
        for(int i=1;i<=juryNumber;i++)
            printf("%d ",Ans[i]);
        printf("\n");
    }
    return 0;
}

• 终于WA了，幸福啊 (0) lizeliang 2009-09-23 12:04:42