我的方法是DP，
定义一个数组：a[205][25][-450..450];
a[i][j][k]:前i个人中，选J个人，D(i) - P(i)差值为K时的最大和。
对于第i个人，显然我们可以不选他，即：a[i-1][j][k]，也可以选他，即:a[i-1][j-1][k-D(i)+P(i)]+D(i)+P(i);
所以得动态转移方程：a[i][j][k]=max{a[i-1][j][j] ,a[i-1][j-1][k-D(i)+P(i)]+D(i)+P(i)};
这样我们就能保证其和最大。
考虑到a[i]只与前面的a[i-1]有关，于是可以用滚动数组来做，否则会MLE。。。

选的时候让k从0到400循环，碰到可以构成的a[n][m][k]即跳出，此时D(i) - P(i)差最小。而此时的a[n][m][k]值即是其最大的和。
关于路径的记录，我们开个  bool used[205][25][-450..450]; 把每次计算时的选择记录下来就行了。输出的时候就根据每次的选择倒过来走。

当然C语言中数组不允许下标为负数，所以我们只能定义成a[205][25][850];这样，然后每次给他加上400再用即可。

• Re:WA了无数次后，终于过了。。。。 (133) gaoteng1984 2007-08-01 09:38:35