题目：http://poj.org/problem?id=1015
DP的第一维是选了几个人，第二维是当前D与P的差值，而值存的是当前D与P的和；
技巧1：通过平移避免负角标，即代码中的fix；
技巧2：做完DP后找出最小的差的绝对值时，如下的那一小段代码很有效率；
技巧3(*)：记录路径——①更新路径时每次判断是否重复选了一个人，重复则不更新；
if(f[j][k]+P[i]+D[i]>f[j+][k+P[i]-D[i]])
{
t1=j;t2=k;
while(t1>&&Path[t1][t2]!=i)//验证i是否在前面出现过
{
t2-=P[Path[t1][t2]]-D[Path[t1][t2]];
t1--;
}
if(t1==)
{
f[j+][k+P[i]-D[i]]=f[j][k]+P[i]+D[i];
Path[j+][k+P[i]-D[i]]=i;
}
}
记录路径1(转)
int tmp=mk;
for(int j=m;j>;j--)
{
int pr=pre[j][tmp];
ans[j]=pr;
tmp-=(a[pr]-b[pr]);
}
sort(ans+,ans+m+);
记录路径1配套输出
②使用vector，每次更新暴力复制；(下面采用)
if(dp[i+][j+subtraction[k]] <= dp[i][j] + _plus[k])
{
dp[i+][j+subtraction[k]] = dp[i][j] + _plus[k];
path[i+][j+subtraction[k]] = path[i][j];//每次更新都要把path全部复制过来，就是因为这个才用的vector
path[i+][j+subtraction[k]].push_back(k);
}
记录路径2(转)
注意：(不知为何)DP顺序，必须是i+1被i更新，原来写的是i被i-1更新，一直WA。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,a[],b[],f[][],fix,t,ans[];
vector<int>pre[][];
int main()
{
while(scanf("%d%d",&n,&m)==)
{
t++;
memset(f,-,sizeof f);
memset(ans,,sizeof ans);
memset(pre,,sizeof pre);
if(!n&&!m)return ;
for(int i=;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
fix=*m;
// for(int k=0;k<=2*fix;k++)f[0][k]=0;
f[][fix]=;
for(int i=;i<=n;i++)//第i个人
for(int j=m-;j>=;j--)//选了j个
for(int k=;k<=*fix;k++)
{
// if(f[j-1][k-a[i]+b[i]]<0)continue;//
// if(f[j][k]<f[j-1][k-a[i]+b[i]]+a[i]+b[i])
// {
// f[j][k]=f[j-1][k-a[i]+b[i]]+a[i]+b[i];
//// pre[j][k]=i;
// pre[j][k]=pre[j-1][k-a[i]+b[i]];
// pre[j][k].push_back(i);
// }
if(f[j][k] >= )
{
if(f[j+][k+a[i]-b[i]]<=f[j][k]+a[i]+b[i])
{
f[j+][k+a[i]-b[i]]=f[j][k]+a[i]+b[i] ;
pre[j+][k+a[i]-b[i]]=pre[j][k];
pre[j+][k+a[i]-b[i]].push_back(i);
}
}
}
int mk;
// for(int k=fix;k<=2*fix;k++)
// if(f[m][k]>0)
// {
// mk=k;break;
// }
// for(int k=fix;k>=0;k--)
// {
// if(fix-k>=mk-fix)break;
// if(f[m][k]>0)
// {
// mk=k;break;
// }
// }
int j=;
while(f[m][fix-j]<&&f[m][fix+j]<)j++;
if(f[m][fix-j]>f[m][fix+j])mk=fix-j;
else mk=fix+j;
int d=(f[m][mk]+(mk-fix))/;
int p=(f[m][mk]-(mk-fix))/;
// int tmp=mk;
// for(int j=m;j>0;j--)
// {
// int pr=pre[j][tmp];
// ans[j]=pr;
// tmp-=(a[pr]-b[pr]);
// }
// sort(ans+1,ans+m+1);
printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n",t,d,p);
for(int i=;i<m;i++)
printf(" %d",pre[m][mk][i]);
printf("\n\n");
}
}