题意略。
思路：
这个题目开始我本来打算用个二维dp，令dp[ i ][ j ]为考虑前i个人，有j个名额的时候，我所能获取的最小差，后来发现不好转移。因为dp[ i ][ j ]有可能是+2，
也有可能是-2，这两种值对我以后的求解可能都有用。后来想再添加一维，dp[ i ][ j ][ 0 ]表示正值的最小，dp[ i ][ j ][ 1 ]表示负值的最小（绝对值的最小）。
这样dp逻辑又很复杂。最后参考了网上的解法，于是将状态定义为:
dp[ i ][ j ][ k ]表示在前i个人里考虑，有j个名额，使得sigma(p) - sigma(d)为k时，我所能获得的sigma(p + d)的最大值。
状态转移方程：dp[ i ][ j ][ k ] = max(dp[i - 1][ j ][ k ] , dp[i - 1][j - 1][k - p[i] + d[i] ] + p[ i ] + d[ i ])
只可惜我做题时只想到了正负值的问题，没有更进一步将正负值直接确定为差值，然后dp对象为p + d，从而满足题目中的第二个条件。
有时dp对象可以是次要条件，而不是首要条件，换一种方向去思考问题。
内存很紧张
//#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int maxn1 = 25; const int maxn2 = 205; const int maxn3 = 805; const int mid = maxn3>>1; const int F = 0x3f; const int INF = 0x3f3f3f3f; struct node{ int peo,place,sub; node(int peo = 0,int place = 0,int sub = 0){ this->peo = peo,this->place = place,this->sub = sub; } }; int p[maxn2],d[maxn2],dp[maxn2][maxn1][maxn3],store[maxn2],n,m; node path[maxn2][maxn1][maxn3]; int main(){ int cas = 1; while(scanf("%d%d",&n,&m) == 2 && (n + m)){ for(int i = 1;i <= n;++i) scanf("%d%d",&p[i],&d[i]); int total = 20 * m; int low = mid - total,up = mid + total; for(int i = 0;i <= n;++i){ for(int j = 0;j <= m;++j){ for(int k = low;k <= up;++k){ dp[i][j][k] = -1; path[i][j][k] = node(-1,-1,-1); } } } for(int i = 0;i <= n;++i) dp[i][0][mid] = 0; for(int i = 1;i <= n;++i){ int bound = min(i,m); for(int j = 1;j <= bound;++j){ for(int k = low;k <= up;++k){ int part1 = dp[i - 1][j][k]; int part2 = (k - p[i] + d[i] < low || k - p[i] + d[i] > up || dp[i - 1][j - 1][k - p[i] + d[i]] == -1) ? -1 : dp[i - 1][j - 1][k - p[i] + d[i]] + p[i] + d[i]; dp[i][j][k] = max(part1,part2); if(part1 == -1 && part2 == -1) continue; if(part1 > part2) path[i][j][k] = node(i - 1,j,k); else path[i][j][k] = node(i - 1,j - 1,k - p[i] + d[i]); } } } int idx; for(int i = 0;i <= total;++i){ int lft = mid - i,rht = mid + i; int maxx = max(dp[n][m][lft],dp[n][m][rht]); if(maxx == -1) continue; if(maxx == dp[n][m][lft]) idx = lft; else idx = rht; if(maxx != -1) break; } int tail = 0; for(int i = n,j = m,k = idx;i != -1;){ node temp = path[i][j][k]; int nxti = temp.peo; int nxtj = temp.place; int nxtk = temp.sub; if(nxti == -1) break; if(nxtj < j) store[tail++] = i; i = nxti,j = nxtj,k = nxtk; } int ans1 = 0,ans2 = 0; for(int i = 0;i < tail;++i){ ans1 += p[store[i]]; ans2 += d[store[i]]; } printf("Jury #%d\n",cas++); printf("Best jury has value %d for prosecution and value %d for defence:\n",ans1,ans2); for(int i = tail - 1;i >= 0;--i) printf(" %d",store[i]); printf("\n\n"); } return 0; } /* 4 2 1 2 2 3 4 1 6 2 10 5 3 8 15 8 11 8 7 8 1 8 17 8 8 8 2 8 13 8 3 8 5 3 13 11 3 17 15 20 6 13 17 9 8 5 3 5 17 16 6 0 17 10 6 14 3 19 4 13 0 17 */
原文：https://www.cnblogs.com/tiberius/p/11257907.html