POJ 1015

  原题的题意是给n个人，每个人对于控辩两方都有一个值，现在选择m个人，使得控辩两方的值的差的和最小，如果有相同的最小值，那么就选择最大的一个。 本题的关键是模型的构建，对于每个人都有两种选择，一个是选择，一个是不选择，对于相同的差值，维护一个最大的和值，换言之，就是假设差值一定，从n个人选择m个人使得和最大.可以转换为背包问题。状态转移的方程为f[i][j][k+p[i]]=max{f[i-1][j][k+p[i]],f[i-1][j-1][k]+v[i]},表示前i个人中选择j个人差的和为k的最大的和的和（p[i]是第i个人的控辩双方的值差，v[i]是第i个人的控辩双方的值和）.本题的另外一个难点在于路径的记录，我们知道，动态规划的一个本质就是状态转移，也就是在当前状态记录是由哪个值推倒过来的，就可以逆序退出上个状态的值。同时通过对路径的遍历，从而可以判断当前的第i个人是否被选择过，从而达到了降维的作用。

#include #include #include #include #include using namespace std;
int a[201],b[201];
int f[30][801],path[30][801];
int p[205],v[205];
bool select(int i,int j,int k)
{
while (true)
{
if (path[i][k]<0 || i<0) break;
if (j==path[i][k]) return true;
k=k-p[path[i][k]];
i–;
}
return false;
}
int main()
{
int n,m;
int No=0;
while (scanf(“%d%d”,&n,&m)!=EOF && n+m!=0){
cout<<”Jury #”<<++No<=0){
for (int j=0;j=0 && f[m][m*20+i]>=f[m][m*20-i])
{
k=m20+i;
break;
}
if (f[m][m20-i]>=0){
k=m20-i;
break;
}
}
int suma=0,sumb=0;
int id[300];
int sum=0;
while (true)
{
int i=path[m–][k];
if (i==-1 || m<0) break;
id[sum++]=i;
suma+=a[i];
sumb+=b[i];
k=k-p[i];
}
cout<<”Best jury has value “< #include #include #include #include using namespace std;
int a[201],b[201];
int f[30][801],path[30][801];
int p[205],v[205];
bool select(int i,int j,int k)
{
while (true)
{
if (path[i][k]<0 || i<0) break;
if (j==path[i][k]) return true;
k=k-p[path[i][k]];
i–;
}
return false;
}
int main()
{
int n,m;
int No=0;
while (scanf(“%d%d”,&n,&m)!=EOF && n+m!=0){
cout<<”Jury #”<<++No<=0){
for (int j=0;j=0 && f[m][m*20+i]>=f[m][m*20-i])
{
k=m20+i;
break;
}
if (f[m][m20-i]>=0){
k=m20-i;
break;
}
}
int suma=0,sumb=0;
int id[300];
int sum=0;
while (true)
{
int i=path[m–][k];
if (i==-1 || m<0) break;
id[sum++]=i;
suma+=a[i];
sumb+=b[i];
k=k-p[i];
}
cout<<”Best jury has value “<