当前位置： 首页 > 编程日记 > 正文

Online Judge上陪审团选人问题用Java实现的一个AC解

编程日记 2024-09-02 14:00:00

原问题位于：http://poj.org/problem?id=1015

以下为问题描述的摘录：

In Frobnia, a far-away country, the verdicts in court trials are determined by a jury consisting of members of the general public. Every time a trial is set to begin, a jury has to be selected, which is done as follows. First, several people are drawn randomly from the public. For each person in this pool, defence and prosecution assign a grade from 0 to 20 indicating their preference for this person. 0 means total dislike, 20 on the other hand means that this person is considered ideally suited for the jury.
Based on the grades of the two parties, the judge selects the jury. In order to ensure a fair trial, the tendencies of the jury to favour either defence or prosecution should be as balanced as possible. The jury therefore has to be chosen in a way that is satisfactory to both parties.
We will now make this more precise: given a pool of n potential jurors and two values di (the defence's value) and pi (the prosecution's value) for each potential juror i, you are to select a jury of m persons. If J is a subset of {1,..., n} with m elements, then D(J ) = sum(dk) k belong to J
and P(J) = sum(pk) k belong to J are the total values of this jury for defence and prosecution.
For an optimal jury J , the value |D(J) - P(J)| must be minimal. If there are several jurys with minimal |D(J) - P(J)|, one which maximizes D(J) + P(J) should be selected since the jury should be as ideal as possible for both parties.
You are to write a program that implements this jury selection process and chooses an optimal jury given a set of candidates.

分析： 每一个candidate可以有被选和未被选两种可能。设O(p,q,diff,sum)表示: 在状态(diff,sum)下，从1, 2, ... p个候选人中选择q个作为陪审团成员的一个最优解, 如果

1）p被选中，那么剩下的q-1个候选人从p-1中选取的方案肯定也是最优的，即O(p,q,diff,sum) = O(p-1,q-1, diff + Ppscore - Pdscore, sum + Ppscore + Pdscore);

2）同样，如果p未被选中，那么剩下的q个候选人从p-1中选取的方案肯定也是最优的，即O(p,q,diff,sum) = O(p-1,q,diff,sum)。

这样最优解就是从这两种情况中选一个符合条件的最佳方案。

这里O(k,0) = {}; O(k,k)={1，2，...，k}

因此符合动态规划(DP)的最优原则。

在计算O(i,j,diff,sum)时并不需要考虑从n, n-1, ..., i+1的组合辩控和（即变量sum)，因为如果有sum1>sum2，那么X + sum1 > X + sum2，而这里X就是从n, n-1, ..., i+1的组合辩控和。当然diff状态必须考虑，因为最终的最优解要求是绝对值，而不是简单和。本人一开始考虑sum，走了一些弯路。


计算顺序举例：如果在动态规划过程(遵循从1,2,...i计算顺序)计算到(i,j)-即从1...i个候选人中选择j个人作为陪审员时，当前状态 i=10,j=6,diff=-5（即代码中的s值: 可变范围diffMin~diffMax），pi=7（控方给第i个候选人的打分）,di=4（辩方给第i个候选人的打分），此时有两个可能最优方案 i=9,j=6,diff=-5（即不选i，记为O(9，6，-5)=代码中的变量prevDs2）和i=9,j=5,diff=-5+(pi- di)=-2（即选i，记为O(9，5，-2)=代码中的变量prevDs1），接下来就要根据这两个可能解的|Diff(1, 2, ...,i)|最小以及Sum(1, 2, ...,i)最大决定取那个解作为最优方案，如果O(9，6，-5)和O(9，5，-2)的最优diff都等于-3，则需要比较下面两个辩控和： 1）第i （i=10）个候选人的辩控和dpiSum + O(9，5，-2)从1,2...9的辩控和prevDs1.sum； 2）O(9，6，-5)从1,2...9的辩控和prevDs1.sum。这里第二个方案中没有包含i。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/*** Author: ljs* 2011 - 05 - 14*  * see also: */
public class Main {class DS{//the global optimal diff of both parties (prosecution and defense)//for the state (i,j,diff)short d;	//the current sum from 1 to ishort sum;//the candidates(1~200): format: (1)(2)....(200)byte[] candNrs;		}class OptimalChoice {		DS[] diffTable;//the offset of the diff tableint offsetDiff; public OptimalChoice(DS[] diffTable,int offsetDiff){this.diffTable = diffTable;this.offsetDiff = offsetDiff;}}class Pair{short nr;short val;Pair(short nr,short val){this.nr =nr;this.val = val;}}	private OptimalChoice[] currLevel;private short[] P,D;//private short n;private short m;private int round;public void selectJury(short[] Ps, short[] Ds, short n, short m) {if (n < m || n != Ps.length || Ps.length != Ds.length)return;this.P = new short[n + 1];System.arraycopy(Ps, 0, P, 1, n);this.D = new short[n + 1];System.arraycopy(Ds, 0, D, 1, n);	//this.n = n;this.m = m;List<Pair> diffPairs = new LinkedList<Pair>();for(int i=1;i<=n;i++){diffPairs.add(new Pair((short)i, (short)(P[i] - D[i])));}Collections.sort(diffPairs,new Comparator<Pair>(){public int compare(Pair o1,Pair o2){if(o1.val>o2.val)return 1;else if(o1.val==o2.val)return 0;elsereturn -1;}});//Runtime rt = Runtime.getRuntime();OptimalChoice[] lastLevel =  null;for (short i = 1; i <= n; i++) {currLevel = new OptimalChoice[m+1];int remainCandidatesCount = n-i;	int removeIdx = -1;for(int k=0;k<diffPairs.size();k++){Pair p = diffPairs.get(k);if(p.nr == i){removeIdx = k;break;}} 		diffPairs.remove(removeIdx);			for (short j = 1; j <= m; j++) {int remainJurorsCount = m-j;if (i >= j && (remainCandidatesCount>=remainJurorsCount)) {	short diffMin = 0;short diffMax = 0;int u=0,v=diffPairs.size()-1;int cnt = 0;while(cnt<remainJurorsCount){diffMin += diffPairs.get(u).val;diffMax += diffPairs.get(v).val;u++;		v--;cnt++;}					short OFFSET_DIFF = (short)-diffMin;			short diffDim = (short)(diffMax - diffMin + 1);	DS[] diffTable = new DS[diffDim];			currLevel[j]=new OptimalChoice(diffTable,OFFSET_DIFF);//only one choice: select all candidates from 1...i						if (i == j) {  if(n-i==m-j && i<n){//go on to upper levelbreak;					}else{short diffTotal = 0;short sumTotal = 0;for(int k=1;k<=i;k++){diffTotal += P[k] - D[k];sumTotal += P[k] + D[k];}			for(short s=diffMin;s<=diffMax;s++){//update the current table DS dsNow = new DS();dsNow.d = (short)(diffTotal + s);dsNow.sum = (short)sumTotal;//dsNow.selected = true;//dsNow.selectAllPrev = true;byte[] candNrs = new byte[i];for(byte k=1;k<=i;k++){candNrs[k-1] = k;}			dsNow.candNrs = candNrs;//update the current tablediffTable[s + OFFSET_DIFF] = dsNow;								}}						} else {/*O(i,j,diff,sum) = minabsOrmaxtotal(O(i-1,j-1,diff+pi-di), O(i-1,j,diff));if diff is equal, check the max in (sum_i + O(i-1,j-1).sum, O(i-1,j).sum)*/ 						// case 1: select iOptimalChoice prevOptimalChoice1 =  lastLevel[j - 1];int dpiDiff1 = P[i] - D[i];int dpiSum = P[i] + D[i];//case 2: not select iOptimalChoice prevOptimalChoice2 = lastLevel[j];for(short s=diffMin;s<=diffMax;s++){DS[] diffTable2 = prevOptimalChoice2.diffTable;						 			//get the prev optimal valueDS prevDs2 = diffTable2[s + prevOptimalChoice2.offsetDiff];int diffNew1 = dpiDiff1 + s;	DS[] diffTable1 = null;if(prevOptimalChoice1 != null)diffTable1 = prevOptimalChoice1.diffTable;DS prevDs1 = null;if(diffTable1 != null)prevDs1 = diffTable1[diffNew1 + prevOptimalChoice1.offsetDiff];int diff1 = 0;			int sum1 = 0;if(prevDs1 ==null){diff1 = Math.abs(diffNew1);sum1 = dpiSum;}else{diff1 = Math.abs(prevDs1.d);	sum1 = dpiSum + prevDs1.sum;}//this case can't be possible//if(prevDs2 ==null){ //	diff2 = Math.abs(s);//	sum2 = 0;//}else{int diff2 = Math.abs(prevDs2.d);	int sum2 = prevDs2.sum;//}int diffNow = s + OFFSET_DIFF;DS dsNow = new DS();boolean choice1 = true;if (diff1 < diff2) {choice1 = true;		}else  if (diff1 > diff2) {// select choice #2choice1 = false;												}else {				if(sum1 >= sum2){choice1 = true;}else{// select choice #2choice1 = false;}			}if(choice1){// select choice #1							if(prevDs1 == null){dsNow.d = (short)diffNew1;}else{dsNow.d = prevDs1.d;				}dsNow.sum = (short)sum1;//dsNow.selected = true;												byte[] candNrs = null;if(prevDs1 != null){candNrs = new byte[prevDs1.candNrs.length+1];									System.arraycopy(prevDs1.candNrs, 0, candNrs, 0, prevDs1.candNrs.length);		candNrs[candNrs.length-1] = (byte)i;}else{candNrs = new byte[1];candNrs[0]= (byte)i;}dsNow.candNrs = candNrs;		}else{//if(prevDs2 == null){//	dsNow.d = s;//}else{dsNow.d = prevDs2.d;											//}dsNow.sum = (short)sum2;												if(prevDs2 != null){byte[] candNrs = new byte[prevDs2.candNrs.length];										System.arraycopy(prevDs2.candNrs, 0, candNrs, 0, prevDs2.candNrs.length);																				dsNow.candNrs = candNrs;}				}diffTable[diffNow] = dsNow;	} 						}					} // i < j is invalid (e.g. n<m is not valid)//remove the last level's items from 1 to j-2:			if(lastLevel!= null && j>=1 && lastLevel[j-1] != null) {	DS[] diffTable = lastLevel[j-1].diffTable;for(int row=0;row<diffTable.length;row++){		diffTable[row] = null;			}//remove the DS items					lastLevel[j-1].diffTable = null;lastLevel[j-1] = null;		}// Collect garbage //rt.gc();}//long availMem = rt.freeMemory()/1000000;//System.out.format("%d mb, i=%d%n", availMem,i);lastLevel = null;lastLevel = currLevel;//rt.gc();//System.gc();}				}public void setRound(int round) {this.round = round;}public void output(){OptimalChoice juryChoiceTable = currLevel[m];DS[] diffSumTable = juryChoiceTable.diffTable;int diff = 0;int offsetDiff = 0;		DS optimal = diffSumTable[diff + offsetDiff];int totalP=0;int totalD=0;byte[] candNrs = optimal.candNrs;List<Short> jurors = new ArrayList<Short>();for(int i=0;i<candNrs.length;i++){short candidateNr = (short)(candNrs[i] & 0x00ff);jurors.add(candidateNr);totalP += P[candidateNr];totalD += D[candidateNr];};Collections.sort(jurors);System.out.println("Jury #"+this.round);System.out.println("Best jury has value "+totalP + " for prosecution and value " + totalD +" for defence:");for(short jurorNr:jurors){System.out.print(" "+jurorNr);}	System.out.println();System.out.println();}public static void main(String[] args) throws Exception {List<short[]> PS =  new ArrayList<short[]>();List<short[]> DS =  new ArrayList<short[]>();List<Short> NS = new ArrayList<Short>();List<Short> MS = new ArrayList<Short>();short[] P=null;short[] D=null;short n=0,m=0;boolean jobsAvail = false;try{Scanner cin=new Scanner(System.in);String line = cin.nextLine();			if(line != null) {				boolean nextRound=true;int candidateLine=0;//int round=1;do{					line = line.trim();		if(line.length()==0){if(P != null && n >0){				PS.add(P);DS.add(D);NS.add(n);MS.add(m);jobsAvail = true;//round++;}//do the next roundnextRound = true;				P = null;D = null;}else{			short[] pair = new short[]{-1,-1};String[] tokens = line.split(" ");for(int i=0,j=0;i<tokens.length;i++){String token = tokens[i].trim();if(token.length()>0 && j<2){pair[j++] = Short.parseShort(token);}}//endif(pair[0]==0 && pair[1]==0){			if(candidateLine<n){P[candidateLine] = pair[0];D[candidateLine++]=pair[1];}else{if(P != null){PS.add(P);DS.add(D);NS.add(n);MS.add(m);jobsAvail = true;}break;				}}else{if(nextRound){nextRound = false;n = pair[0];m = pair[1];P = new short[n];D = new short[n];candidateLine=0;}else{if(candidateLine<n){P[candidateLine] = pair[0];D[candidateLine++]=pair[1];}}}						}					line = cin.nextLine();}while(line !=null);}}catch(Exception e){throw e;}if(jobsAvail){			for(int i=0;i<PS.size();i++){Main js = new Main();js.setRound(i+1);js.selectJury(PS.get(i), DS.get(i), NS.get(i),MS.get(i));js.output();}}}
}

测试：

4 2 // sample input
 1  2
 2  3
 4  1
 6  2

5 3   // prosecution > defense
13 11
 3 17
15 20
 6 13
17  9

8 5   // prosecution < defense
 3  5
17 16
 6  0
17 10
 6 14
 3 19
 4 13
 0 17

8 4    // prosecution == defense
19 18
 5  9
 0  9
 5  0
 4  4
16  9
 4 15
20  5

2 1  // two solutions with diffence 1, but one of them
1 2  // has a larger value (version 1)
4 3

2 1  // two solutions with diffence 1, but one of them
4 3  // has a larger value (version 2)
1 2

2 1  // two solutions with diffence 1, but one of them
3 4  // has a larger value (version 3)
1 2

2 1  // two solutions with diffence 1, but one of them
2 1  // has a larger value (version 4)
3 4

18 7  // only differences +1,0,-1 occur with diffenent
 1  1 // sums (of values). Make sure that we are really
 1  2 // selecting the maximum sum.
 2  1
10 10
11 10
10 11
 7  7
 7  8
 8  7
14 14
14 15
15 14
 4  4
 4  5
 5  4
19 19
19 20
20 19

21 13 // all possible pairs of equal values: (0,0),...(20,20)
20 20 // again, there are many solutions with difference 0, but
19 19 // we want the one with maximum total value!
18 18
14 14
13 13
 5  5
 4  4
 3  3
12 12
10 10
 9  9
 8  8
17 17
16 16
15 15
 7  7
 6  6
11 11
 2  2
 1  1
 0  0

10 10 // n = m
 8 16
 9  6
 6  6
 2 15
 0 13
17  8
17  3
13 13
15 10
18  2

10 9  // n = m+1
12 13
16 17
 2  7
 1  9
 5  7
10  9
 9  8
 9 19
 2 10
 3 19

10 8  // n = m+2
14  4
18 17
20 12
10 16
 8 14
 1 16
 9 10
16 11
 4  2
10 16

10 5  // partition problem: note that the values of
 3  8 // both parties add up to 80. There exits a solution
15  8 // with diffence 0 iff the prosections values can be
11  8 // divided in two subsets with sum 40 each. This
 7  8 // example shows how to reduce BI-PARTITION to this
 1  8 // problem and therefore show its NP-completeness.
17  8
 8  8
 2  8
13  8
 3  8

1 1  // now for the boundary test: first comes n=m=1
9 11

1 1
7 3

1 1
5 5

1 1
0 0

1 1
0 20

1 1
20 0

1 1
20 20

20 20 // now comes n=m=20.
0 0   // first 20 times (0,0), then (0,20), (20,0) and (20,20)
0 0   // finally a random sample
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

20 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20

20 20
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0

20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20

20 20
 7 20
10  1
14 17
11 13
 3  5
19 19
 1 16
 4 18
 9  1
13  3
 7 16
 6  3
 1 20
 4  5
 6 13
 6  8
10  9
11 11
 0  7
12 15

200 20 // and now for maximum values: n = 200, m = 20.
0 0    // again a five test series as above
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

200 20
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0
20 0

200 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20

200 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20
20 20

200 20
12 20
10  0
13 17
15  1
 8 12
 4 12
 9  5
 3  3
13 18
13  6
12 11
10  6
 3  1
 6  1
20  2
20 18
19  2
12 12
 1  8
12  6
 6 11
11 16
11  0
 2  1
 7  6
15  6
13  7
16 17
 5 11
 0 14
17  8
10  9
12 14
 9  9
20  2
13  4
 5 19
17  0
 2 12
13  8
 4 17
 5  3
11 19
 6  9
 1  3
 5 10
18  0
 6  6
 2  8
20 11
 0  8
 5  1
12 17
17  8
 9 12
 9 10
 3  0
 0 19
20  9
15 16
 4  6
 1  1
19 13
 9 17
 0  8
 1  4
19 14
 1  6
16 14
12 12
19 18
19 19
 3 17
 9 17
 4  6
16 19
14  3
 9  4
13 19
 3 16
19  9
 0  2
 8  9
10 10
15  3
16  2
16  4
12  6
13  0
 8  0
11  8
18 15
18 18
 2 20
 7  2
14  1
 3  0
 0 15
11 16
 0 18
 1 17
11 11
 9  9
19  6
 6  1
18 13
19  8
 9  0
 2 18
16  9
18 12
10 13
12 13
16  5
 7 17
 5  4
13  8
 0  4
 8 19
12 14
 0  2
 6 19
 9  0
18  6
 7 19
18 19
15  7
 9 12
12  5
 0  1
15 15
 1 16
20 16
10 10
11  2
 7  4
16 12
16  0
 4  3
17 18
 8 14
13  7
 5 19
14 20
19 15
 5 19
18  7
 6  9
 0  2
 7  3
11 14
 7  0
 8  5
18 15
 0  2
11  2
11 17
11  8
 5 16
 5 13
12 12
 8  6
20 14
13 14
 0  1
10 15
12 17
14 15
 2  6
17 14
 6 13
10 10
13  6
 6 16
15 11
 4  5
15 18
11 13
19 20
 2  0
12  9
14  2
10 20
 0  7
16  2
16 13
20 17
14  6
 5 15
 7 19
17 10
 0 19
13 15
17 18
19  9
14  1
15  2
 8  8
 2 15
20  2

200 10 // and another large test, n=200,m=10
16 11
 9 10
 2 19
 2 18
 8  7
18  3
 9 16
10  3
16  3
 9 16
 4 14
10  0
10 13
 7  1
 5  3
 4 19
 9  1
 7  4
19 20
10  5
19 13
 9  5
12  4
18 12
 4 12
 0  8
 3  0
10 18
 6 19
 3  3
17  8
12 17
 5  3
16  4
 4 10
 8 18
17 17
18  9
 6  0
20  6
 8 13
 8  2
16 17
18  7
14  0
 0  3
14  0
10 11
 9 12
 7  9
 1  8
16 19
20 18
14 19
17 11
16  3
11 11
 5  1
19  4
 0 20
12 18
19 18
 7 16
 9  2
17 17
 5  7
 6 12
 9 18
17  4
 6  7
20  7
10  6
14  3
13 13
16 15
 6  0
19  7
15  6
16 19
20 17
17  0
12 18
 7  6
16  8
 5 17
10 15
 1  5
 4 19
 1  6
12  6
 4 10
 5  9
16  5
 8 17
 4  3
 1  6
 6  5
 3 19
13  6
11  1
 4  9
 1 19
 6  3
10 11
13  8
 0 13
 5  9
 1 10
13 19
15  0
 1 10
13  9
 6 13
16  3
 2 17
13 20
12  7
10 18
12 12
15 18
 4 18
14 10
17 18
11  2
 5  2
15 15
19 14
12  5
18 19
19 12
 5 17
 9 20
12  0
19 13
14  7
 2 16
 7 11
15 15
 8  6
 8  2
 1 13
18 15
 1  2
17 20
 4 19
 9 16
10 12
 7 12
 9  3
 5 14
 0 12
14 10
 1 11
12 18
16 16
10 15
 7  8
 9 10
13  7
11 14
 6  3
 7 20
16  4
17  1
 6  7
12 11
18  1
 6 19
10 15
15 12
 1 17
12  3
13 16
14 14
15  1
18  8
19 15
 6 15
12  9
14 16
 7  7
11  0
 1 20
16 13
15  3
 5 13
 9 11
12 15
20 16
 2 17
 1 19
17 15
12  5
16  2
 2  2
19  9
15  0
20 11
18 12
14  5


0 0
Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
 2 3

Jury #2
Best jury has value 36 for prosecution and value 33 for defence:
 1 4 5

Jury #3
Best jury has value 50 for prosecution and value 53 for defence:
 2 3 4 5 7

Jury #4
Best jury has value 33 for prosecution and value 33 for defence:
 2 5 7 8

Jury #5
Best jury has value 4 for prosecution and value 3 for defence:
 2

Jury #6
Best jury has value 4 for prosecution and value 3 for defence:
 1

Jury #7
Best jury has value 3 for prosecution and value 4 for defence:
 1

Jury #8
Best jury has value 3 for prosecution and value 4 for defence:
 2

Jury #9
Best jury has value 111 for prosecution and value 111 for defence:
 4 10 11 12 16 17 18

Jury #10
Best jury has value 182 for prosecution and value 182 for defence:
 1 2 3 4 5 9 10 11 12 13 14 15 18

Jury #11
Best jury has value 105 for prosecution and value 92 for defence:
 1 2 3 4 5 6 7 8 9 10

Jury #12
Best jury has value 66 for prosecution and value 99 for defence:
 1 2 3 4 5 6 7 8 9

Jury #13
Best jury has value 93 for prosecution and value 94 for defence:
 1 2 3 4 6 8 9 10

Jury #14
Best jury has value 40 for prosecution and value 40 for defence:
 2 4 8 9 10

Jury #15
Best jury has value 9 for prosecution and value 11 for defence:
 1

Jury #16
Best jury has value 7 for prosecution and value 3 for defence:
 1

Jury #17
Best jury has value 5 for prosecution and value 5 for defence:
 1

Jury #18
Best jury has value 0 for prosecution and value 0 for defence:
 1

Jury #19
Best jury has value 0 for prosecution and value 20 for defence:
 1

Jury #20
Best jury has value 20 for prosecution and value 0 for defence:
 1

Jury #21
Best jury has value 20 for prosecution and value 20 for defence:
 1

Jury #22
Best jury has value 0 for prosecution and value 0 for defence:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Jury #23
Best jury has value 0 for prosecution and value 400 for defence:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Jury #24
Best jury has value 400 for prosecution and value 0 for defence:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Jury #25
Best jury has value 400 for prosecution and value 400 for defence:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Jury #26
Best jury has value 154 for prosecution and value 220 for defence:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Jury #27
Best jury has value 0 for prosecution and value 0 for defence:
 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

Jury #28
Best jury has value 400 for prosecution and value 0 for defence:
 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

Jury #29
Best jury has value 0 for prosecution and value 400 for defence:
 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

Jury #30
Best jury has value 400 for prosecution and value 400 for defence:
 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

Jury #31
Best jury has value 350 for prosecution and value 350 for defence:
 1 16 28 60 71 72 76 92 93 126 133 140 144 145 154 163 177 179 187 194

Jury #32
Best jury has value 182 for prosecution and value 182 for defence:
 19 43 53 62 79 80 123 129 144 189

转载于:https://www.cnblogs.com/ljsspace/archive/2011/06/05/2073355.html


https://www.dkcj.cn/info/16969.html

相关文章：

【D3】transition API

摘要&#xff1a; 动画类API 一、API 使用 1. 1 d3.ease 1.2 d3.timer Start a custom animation timer, invoking the specified function repeatedly until it returns true. There is no way to cancel the timer after it starts, so make sure your timer function return…

编程日记2024/09/02 13:50:00

微信小程序 - 富文本图片宽度自适应（正则）

引言&#xff1a;在微信小程序里&#xff0c;比如商品展示页面的商品详情会有图片展示&#xff0c;PC端设置的商品详情是PC端的宽度&#xff0c;所以在小程序里图片会显示不全&#xff0c;这时就应该做相应的处理&#xff0c;使小程序里图片显示正确 思路 把图片的宽度改为手机…

编程日记2024/09/02 13:40:00

（1）01背包问题

#include <stdio.h> #define N 6 #define M 21 #define W 20 int dp[N][M]; int w[N] {0}; int v[N] {0}; void knapsack(){int i, j;int value1, value2;for(i 1; i < N; i){ // 前i件物品for(j 1; j < N; j){ // 背包剩余空间if(w[i] > j){ // 第i件物品太…

编程日记2024/09/02 13:30:00

Web.Config文件配置之限制上传文件大小和时间

在邮件发送系统或者其他一些传送文件的网站中&#xff0c;用户传送文件的大小是有限制的&#xff0c;因为这样不但可以节省服务器的空间&#xff0c;还可以提高传送文件的速度。下面介绍如何在Web.Config文件中配置限制上传文件大小与时间。 在Web.Config文件中配置限制上传文件…

编程日记2024/09/02 13:20:00

成为软件高手的几个忌讳

1&#xff09; 不会英语&#xff1a;CS源于美国&#xff0c;重量级的文档都是英文的。不会英语&#xff0c;那么你只能忍受拙劣的翻译和大延迟的文档&#xff08;翻译出来的文档几乎都是很久以前出版的东西&#xff09;。2&#xff09; 急于求成&#xff1a;什么都没学习就开始…

编程日记2024/09/02 13:10:00

Linux下的redis的持久化,主从同步及哨兵

redis持久化 Redis是一种内存型数据库&#xff0c;一旦服务器进程退出&#xff0c;数据库的数据就会丢失&#xff0c; 为了解决这个问题&#xff0c;Redis提供了两种持久化的方案&#xff0c;将内存中的数据保存到磁盘中&#xff0c;避免数据的丢失。 RDB持久化 redis提供了RDB…

编程日记2024/09/02 13:00:00

vue/require-v-for-key]Elements in iteration expect to have ‘v-bind:key‘ directives

报错内容&#xff1a;[vue/require-v-for-key]Elements in iteration expect to have v-bind:key directives.解决&#xff1a;加上v-bind:key"index"<p>主演:<!--显示电影主演&#xff0c;循环--><span v-for"(actor, index) in scope.row.act…

编程日记2024/09/02 12:50:00

@Ignore_JUnit - Ignore Test

Ignore 用法很简单, 如果你的测试用例还没有准备好而不想被执行, 又不想删掉或注释掉, 可以使用 Ignore 标注来忽略测试。 方法一旦用 Ignore 注解了将不会被执行. 如果一个类用 Ignore 注解了 他下面的所有测试方法将不会被执行. 看个应用 Create a Class Create a java clas…

编程日记2024/09/02 12:40:00

Redis5.0之Stream案例应用解读

2019独角兽企业重金招聘Python工程师标准>>> 非常高兴有机会和大家在这里交流Redis5.0之Stream应用。今天的分享更多的是一个抛砖引玉&#xff0c;欢迎大家提出更多关于Redis的思考。 首先&#xff0c;我们来个假设&#xff0c;这里有个杯子&#xff0c;这个杯子是去…

编程日记2024/09/02 12:30:00

往阿里云服务器上安装Mysql

在安装完Mysql后要进行登录&#xff0c;这时候显示让你输密码&#xff0c; 我点击键盘发现怎么没有密码出现&#xff0c; 然后我就把Mysql卸载了重新装的&#xff0c;折腾了2个多小时&#xff0c; 最后&#xff0c;我突然想试试直接输密码然后就回车&#xff0c; 发现成功进入数…

编程日记2024/09/02 12:20:00

PHP中spl_autoload_register函数的用法

spl_autoload_register(PHP 5 > 5.1.2)spl_autoload_register — 注册__autoload()函数说明bool spl_autoload_register ([ callback $autoload_function ] )将函数注册到SPL __autoload函数栈中。如果该栈中的函数尚未激活&#xff0c;则激活它们。如果在你的程序中已经实现…

编程日记2024/09/02 12:10:00

Linux初步——常用简单命令

散乱的记录&#xff0c;目前是边学边用&#xff0c;以后有机会再整理 curl命令 发起一个HTTP请求&#xff0c;如&#xff1a;curl "http://www.baidu.com" 加上-I选项查看HTTP协议头的信息&#xff0c;如&#xff1a;curl "http://www.baidu.com" -I Linux…

编程日记2024/09/02 12:00:00

Centos-Mysql配置my.cnf内容

#v1.0 [mysqld] #通用 #skip-grant-tables 跳过授权密码登录 port3306 #使用mysql系统账号操作进程 usermysql socket/var/lib/mysql/mysql.sock #basedir/usr datadir/var/lib/mysql #mysql错误日志 log_error /tmp/ch_mysql_log/error.log #mysql所有操作日志 生产服务器不…

编程日记2024/09/02 11:50:00

本地navicat连接阿里云数据库

自己起连接名字&#xff1b; prot:填公网IP&#xff08;服务器给的&#xff09; password&#xff1a;填阿里云数据库的密码

编程日记2024/09/02 11:40:00

adb logcat命令查看并过滤android输出log

adb logcat命令查看并过滤android输出log cmd命令行中使用adb logcat命令查看android系统和应用的log&#xff0c;dos窗口按ctrlc中断输出log记录。 logcat日志中的优先级/tag标记&#xff1a; android输出的每一条日志都有一个标记和优先级与其关联。 优先级是下面的字符&…

编程日记2024/09/02 11:30:00

重读TCP协议（3）

重读TCP协议&#xff08;3&#xff09; TCP 的数据流TCP的数据流大致可以分为两类&#xff0c;交互数据流与成块的数据流。交互数据流就是发送控制命令的数据流&#xff0c;比如relogin&#xff0c;telnet&#xff0c;ftp命令等等&#xff1b;成块数据流是用来发送数据的包&…

编程日记2024/09/02 11:20:00

拥有2000家门店，他如何晋升为服装界的新宠？

—— iwarm3.0加热组件、碳纳米管膜炎、管状石墨结构体...你看到并不是一款高科技电子产品&#xff0c;这是快鱼服饰在这个冬天推出的黑科技产品 - 智能温控羽绒服。 在竞争激烈的服装行业&#xff0c;快鱼&#xff08;Fast Fish&#xff09;将“快时尚”的理念推广至全国&…

编程日记2024/09/02 11:10:00

navicat连接云数据库报错2003，2005

一开始报2003&#xff0c;好吧&#xff0c;是Mysql挂掉了&#xff0c; 然后重启Mysql服务 systemctl restart mysqld.service #重启 mysql然后再连接&#xff0c;报错2005&#xff0c; 好吧&#xff0c;是复制ip的时候多了一个空格&#xff0c;再输入一次即可 我服了。

编程日记2024/09/02 11:00:00

基础学习总结（四）--SQLite

1. SQLiteDatabase操作SQLite数据库的类。可以执行SQL语句&#xff0c;对数据库进行增、删、查、改的操作。也可以进行transaction的控制。很多类对数据库的操作最终都是通过SQLiteDatabase实例来调用执行的。需要注意的是&#xff0c;数据库对于一个应用来说是私有的&#xff…

编程日记2024/09/02 10:50:00

用node实现websocket协议

协议 WebSocket是一种基于TCP之上的客户端与服务器全双工通讯的协议&#xff0c;它在HTML5中被定义&#xff0c;也是新一代webapp的基础规范之一。 它突破了早先的AJAX的限制&#xff0c;关键在于实时性&#xff0c;服务器可以主动推送内容 到客户端&#xff01;可能的应用有&a…

编程日记2024/09/02 10:40:00

反向春运成为新趋势 客流年增9%

资料图&#xff1a;春运。殷立勤 摄 中新社北京1月18日电 (记者 周音)近年来&#xff0c;反向春运成为新趋势。中国铁路总公司18日披露&#xff0c;反向春运客流以年增9%左右的速度增长。 传统春运是大城市返乡回家过年。反向春运是年轻人选择将老家的父母和孩子接来自己工作的…

编程日记2024/09/02 10:30:00

把.sql文件上传到服务器上

使用xftp工具&#xff0c;在root文件夹下新建myProject文件夹&#xff0c;然后把.sql文件拖拽过去即可。 进入xshell&#xff0c; 进入到mysql&#xff1a; mysql -u root -p输入密码&#xff1a; create database 数据库名&#xff1b;use 数据库名&#xff1b;source ~/新…

编程日记2024/09/02 10:20:00

最先进的开源游戏引擎KlayGE 3.12.0发布

转载请注明出处为KlayGE游戏引擎&#xff0c;本文地址为http://www.klayge.org/2011/06/30/%e6%9c%80%e5%85%88%e8%bf%9b%e7%9a%84%e5%bc%80%e6%ba%90%e6%b8%b8%e6%88%8f%e5%bc%95%e6%93%8eklayge-3-12-0%e5%8f%91%e5%b8%83/ KlayGE 3.12.0在上半年的最后一天发布了&#xff01…

编程日记2024/09/02 10:10:00

如何防止博客文章被窃取

写文章的优点&#xff1a; 1.整理自己的学习过程&#xff0c;思想心得。 2.看到自己的文章被别人转载了&#xff0c;心理愉悦&#xff0c;说明作者写的文章有价值&#xff0c;可以帮助他人。 缺点&#xff1a; 1.花费时间和精力。 2.说是抄袭别人。明明自己是原创&#xff0c;别…

编程日记2024/09/02 10:00:00

js中的装饰器执行顺序

/*** 执行顺讯* [(property)...]->[(parameter->method)...]->constructor->class* [属性...]->[((方法参数...)->方法)...]->[constructor...]->class* 声明周期 property|parameter|method|constructor|class* 声明周期 [始化完毕]init->[属性添加…

编程日记2024/09/02 09:50:00

关于springboot vue前后端分离项目部署到阿里云轻量服务器（前后端分开部署）

0.购买阿里云服务器 1.安装jdk 使用yml安装 2.安装mysql 3.安装nginx 4.打包后端项目 后端项目更改&#xff1a; 在pom.xml文件中&#xff0c;增加打包成jar包的配置文件 application.properties配置文件中更改数据库信息&#xff0c;端口号&#xff1a;&#xff08;所使…

编程日记2024/09/02 09:40:00

.NET泛型解析(下)

上一篇对.NET中的泛型进行了详细的介绍以及使用泛型的好处是什么,这篇将更加深入的去了解泛型的其他的知识点,重头戏. 【1】泛型方法 上一篇我们也说过了,泛型可以是类,结构,接口,在这些泛型类型中定义的方法都可以叫做泛型方法,都可以引用由泛型类型本身指定的一个类型参数例如…

编程日记2024/09/02 09:30:00

spark集群使用hanlp进行分布式分词操作说明

本篇分享一个使用hanlp分词的操作小案例&#xff0c;即在spark集群中使用hanlp完成分布式分词的操作&#xff0c;文章整理自【qq_33872191】的博客&#xff0c;感谢分享&#xff01;以下为全文&#xff1a;分两步&#xff1a;第一步&#xff1a;实现hankcs.hanlp/corpus.io.IIO…

编程日记2024/09/02 09:20:00

让VirtualBox的虚拟机器在电脑开机时自动启动

当你安装很多套Virtualbox的虚拟机器系统后&#xff0c;希望能在开机后自动启动虚拟机器的系统。 Linux (Host OS):在你的/etc/rc.local中加入下列几行VBoxVRDP -startvm WinXP & VBoxVRDP -startvm Win2003 & VBoxVRDP -startvm LinuxFC6 & Windows (Host OS): 开…

编程日记2024/09/02 09:10:00

L1-025 正整数A+B

不确定的点&#xff1a; 1.数据用什么类型输入&#xff0c;如果用字符串类型输入&#xff0c;怎么判断它是不是正整数 2.怎么判断哪部分是A&#xff0c;哪部分是B 解析 c语言’\0’ 意思&#xff1a; 字符常量占一个字节的内存空间。字符串常量占的内存字节数等于字符串中字节…

编程日记2024/09/02 09:00:00