PKU ACM 1015(Jury Compromise)的动态规划解法(JAVA兑现)

PKU ACM 1015(Jury Compromise)的动态规划解法(JAVA实现)

package problem1015;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	
	static int candidateNum;
	static int jurMemNum;
	
	static int [] sub;
	static int [] plus;
	static int totValRangeSize;
	static int totValDelta;
	/*F[i][j] means among i candidates, the maximum D(J) + P(J) while |D(J) - P(J)| = j
	 F[i][j] = -1 if no J satisfy |D(J) - P(J)| = j within i candidates
	 */
	static int [][] dp;
	static int [][] path;// index of the last candidate put in when updating dp[i][j]
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int caseCtr = 0;
		
		while(true)
		{
			caseCtr++;
			
			candidateNum = scanner.nextInt();
			jurMemNum = scanner.nextInt();
			if(candidateNum == 0 || jurMemNum == 0)
				break;
			
			sub = new int[candidateNum];
			plus = new int[candidateNum];
			
			for(int i = 0; i < candidateNum; i++)
			{
				int pros = scanner.nextInt();
				int def = scanner.nextInt();
				sub[i] = pros - def;
				plus[i] = pros + def;
			}
			
			System.out.println("Jury #" + caseCtr);
			solve();
		}
	}
	
	static void solve()
	{
		totValRangeSize = 21 * jurMemNum * 2 + 1;
		totValDelta = 21 * jurMemNum;
		
		dp = new int[jurMemNum + 1][totValRangeSize];
		path = new int[jurMemNum + 1][totValRangeSize];
		
		for(int i = 0; i < jurMemNum + 1; i++)
		{
			for(int j = 0; j < totValRangeSize; j++)
			{
				dp[i][j] = -1;
				path[i][j] = -1;
			}
		}
		
		for(int i = 0; i < candidateNum; i++)
		{
			if(plus[i] > dp[1][totValDelta + sub[i]])
			{
				dp[1][totValDelta + sub[i]] = plus[i];
				path[1][totValDelta + sub[i]] = i;
			}
		}
		
		//Bottom-Top
		for(int i = 1; i < jurMemNum; i++)
		{
			for(int j = 0; j < totValRangeSize; j++)
			{
				if(dp[i][j] > -1)
				{
					for(int k = 0; k < candidateNum; k++)
					{
						if(dp[i][j] + plus[k] > dp[i + 1][j + sub[k]])
						{
							int index1 = i;
							int index2 = j;
							
							while(index1 != 0)
							{
								if(k == path[index1][index2])
									break;
								index2 = index2 - sub[path[index1][index2]];
								index1--;
							}
							
							if(index1 == 0)
							{
								dp[i + 1][j + sub[k]] = dp[i][j] + plus[k];
								path[i + 1][j + sub[k]] = k;
							}
						}
					}
				}				
			}
		}
		
		for(int i = 0; i < totValDelta; i++)
		{
			if(dp[jurMemNum][totValDelta - i] > -1 || dp[jurMemNum][totValDelta + i] > -1)
			{
				if(dp[jurMemNum][totValDelta - i] > dp[jurMemNum][totValDelta + i])
					outputResult(totValDelta - i);
				else
					outputResult(totValDelta + i);
				break;
			}				
		}
	}

	private static void outputResult(int val) {
		ArrayList<Integer> selected = new ArrayList<Integer>();
		int jurSize = jurMemNum;
		int totVal = val;
		int subSum = 0;
		int plusSum = 0;
		
		while(jurSize != 0)
		{
			int candi = path[jurSize][totVal];			
			selected.add(candi + 1);
			subSum += sub[candi];
			plusSum += plus[candi];
			
			totVal -= sub[candi];
			jurSize--;
		}
		
		Collections.sort(selected);
		
		System.out.println("Best jury has value " + (int)((subSum + plusSum) / 2) + " for prosecution and value " + (int)((plusSum - subSum) / 2) + " for defence:");
		for(int i = 0; i < selected.size(); i++)
		{
			System.out.print(" " + selected.get(i));
		}
		System.out.println();
		System.out.println();
	}
}