02979: 陪审团的人选
dp, http://cs101.openjudge.cn/practice/02979
在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：
控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。
输入
输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意，1≤ n≤ 200, 1≤ m≤ 20 而且 m≤ n。接下来的n行，每行表示一个候选人的信息，它包含2个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0
输出
对每组数据，先输出一行，表示答案所属的组号,如 'Jury #1', 'Jury #2', 等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。
样例输入
4 2
1 2
2 3
4 1
6 2
0 0样例输出
Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3来源：Southwestern European Regional Contest 1996, POJ 1015, 程序设计实习2007
【思路】：为叙述问题方便，现将任一选择方案中，辩方总分和控方总分之差简称为“辩控差”，辩方总分和控方总分之和称为“辩控和”。
设
设p为控方分数, d为辩方分数，
有转移式： $ f[j][k] = max(f[j-1][k-v(i)] + s(i))$
转移式表示第j个人选i，且i必须要满足在
用
差值会为负值，因此将差值全部偏移N个单位。
# 陪审团的人选, http://cs101.openjudge.cn/practice/02979/
maxn = 400 + 10 # -20 X m <= maxn <= 20 X m, where 1<=m<=20
cnt = 0
while True:
try:
n, m = map(int, input().split())
except ValueError: #跳过空行
continue
if n + m == 0:
break
p = [0] # 控方分数
d = [0] # 辩方分数
for _ in range(n):
tp, td = map(int, input().split())
p.append(tp)
d.append(td)
cnt += 1
if n == m:
prosecution = sum(p)
defence = sum(d)
print('Jury #{}'.format(cnt))
print("Best jury has value {} for prosecution and value {} for defence:".format(prosecution, defence))
print(' '.join(map(str, range(1,n+1))))
continue
#f = [] 转移方程：f[j][k]=f[j-1][x]+d[i]+p[i]; 且k=x+p[i]-d[i], f[j-1][x]是满足条件的最大值
#path = [] 记录j个人评审差为k,这种情况下的前一个人j-1是谁
result = [None] * maxn
f = [[-1]*5*maxn for _ in range(m+1)]
path = [[0]*5*maxn for _ in range(m+1)]
minP_D = 20 * m # 避免下标为负,所以推广到零以上.题目中的辩控差为0，对应于程序中的辩控差为20*m
f[0][minP_D] = 0 # 初始化条件. 选0个人使得辩控差为nMinP_D的方案，其辩控和就是0
for j in range(m): # 每次循环选出第j个人，共要选出m人
for k in range(minP_D*2 + 1): # 可能的辩控差为[0，nMinP_D*2]
if f[j][k] >= 0: # 方案 f(j,k)可行
for i in range(1, n+1): # 在方案f(j,k)的基础上，挑下一个人，逐个试
if (f[j][k] + p[i] + d[i]) > (f[j+1][k+p[i]-d[i]]):
t1 = j
t2 = k
# 第i个人是否已经在方案f(j,k)中被选上了
while (t1 > 0) and (path[t1][t2] != i):
t2 = t2 - p[path[t1][t2]] + d[path[t1][t2]]
t1 -= 1
# 说明第i个人在方案f(j,k)中没有被选上，那么就选它
# 形成方案f(j+1,k+p[i]-d[i])
if t1 == 0:
# 记录新方案的辩控和
f[j+1][k+p[i]-d[i]] = f[j][k] + p[i] + d[i]
# 选了第i 个人，就要将其记录在path里
path[j+1][k+p[i]-d[i]] = i
#i = minP_D
j = k = 0
# determine minimum possible |D(J)-P(J)|
# 找选了m个人，且实际辩控差绝对值最小的方案。最终方案的程序中辩控差为k
while (f[m][minP_D+j] < 0) and (f[m][minP_D-j] < 0):
j += 1
if f[m][minP_D+j] > f[m][minP_D-j]: # 计算k
k = minP_D + j
else:
k = minP_D - j
# sum(pi) + sum(di) = f(j,k) (1)
# sum(pi) - sum(di) = k - minP_D (2)
# sum(pi) = ((1) + (2)) // 2
# sum(di) = ((1) - (2)) // 2
prosecution = (k - minP_D + f[m][k]) // 2
defence = (minP_D - k + f[m][k]) // 2
print('Jury #{}'.format(cnt))
print("Best jury has value {} for prosecution and value {} for defence:".format(prosecution, defence))
# 最终方案f(m, k)的最后一个人选记录在Path[m][k]中，
# 那么从Path[m][k]出发，顺藤摸瓜就能找出方案f(m, k)的所有人选
for i in range(1, m+1):
result[i] = path[m - i + 1][k]
a = result[i]
b = p[a] - d[a]
k = k - b
ans = []
for i in range(1, m+1):
if result[i] != None:
ans.append(result[i])
ans = sorted(ans) # 按人选编号从小到大排序，以便按要求输出
print(' '.join(map(str, ans)))