Poj Solution 1015

http://poj.org/problem?id=1015

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main{
 static short[] p,d;
 static short[][][] arr,path;
 static int add,a,b,st,ed;
 public static void main(String[] args)
{
 Scanner in=new Scanner(System.in);
 int cnt=0;
 while(true)
 {
  cnt++;
  a=in.nextInt();
  b=in.nextInt();
  if(a==0&&b==0)break;
   System.out.println("Jury #"+cnt);
   p=new short[a+1];
   d=new short[a+1];
   for(int i=1;i<=a;i++)
   {
    p[i]=in.nextShort();
    d[i]=in.nextShort();
    }
    dp();
    for(int k=0;k<=add;k++)
    {
    if(arr[a][b][add+k]>arr[a][b][add-k])
    {
        System.out.println("Best jury has value "+((arr[a][b][add+k]+k)/2)+
            " for prosecution and value "+((arr[a][b][add+k]-k)/2)+" for defence:");
        print(a,b,k);
        break;
    }
    else if(arr[a][b][add-k]!=-1)
    {
        System.out.println("Best jury has value "+((arr[a][b][add-k]-k)/2)+
            " for prosecution and value "+((arr[a][b][add-k]+k)/2)+" for defence:");
        print(a,b,-k);
        break;
    }
    }
    System.out.println();
    System.out.println();
   }
  }

 static void dp()
 {
  arr=new short[a+1][b+1][40*b+30];
  path=new short[a+1][b+1][40*b+30];
  add=20*b;
  st=-b*20;ed=-st;
  for(int i=0;i<=a;i++)
    for(int j=0;j<=b;j++)
        for(int k=st;k<=ed;k++)
            arr[i][j][k+add]=-1;
   arr[0][0][add]=0;
  for(int i=1;i<=a;i++)
    for(int j=0;j<=b;j++)
        for(int k=st;k<=ed;k++)
        {
          arr[i][j][k+add] = arr[i-1][j][k+add];
          path[i][j][k+add]=1;
          if(j>0&&k-p[i]+d[i]>=-add&&k-p[i]+d[i]<=add&&arr[i-1][j-1][k-p[i]+d[i]+add]!=-1
            &&arr[i-1][j-1][k-p[i]+d[i]+add]+p[i]+d[i]>arr[i][j][k+add])
          {
            arr[i][j][k+add]=(short) (arr[i-1][j-1][k-p[i]+d[i]+add]+p[i]+d[i]);
            path[i][j][k+add]=2;
          }
        }
  }

    static void print(int i,int j,int k)
    {
        if(i == 0 && j == 0 && k == 0) return ;
        if(path[i][j][k+add] == 1)
           print(i-1, j, k);
        else{
           print(i-1, j-1, k-p[i]+d[i]);
           System.out.print(" "+i);
        }
    }
}