论坛网站建设视频,wordpress百度自动,河北做网站哪家公司好,精湛的网站建设排行榜正题
题目链接:http://poj.org/problem?id1015 题目大意
每个人有A值和B值#xff0c;要求选M个人#xff0c;使这M个人的|SumA−SumB||SumA−SumB|最小。 解题思路
我们用SumA−SumBSumA−SumB作为原本的价格#xff0c;然后用fi,jfi,j表示已经选了i个人#xff0c;Su…正题
题目链接:http://poj.org/problem?id1015 题目大意
每个人有A值和B值要求选M个人使这M个人的|SumA−SumB||SumA−SumB||Sum_A-Sum_B|最小。 解题思路
我们用SumA−SumBSumA−SumBSum_A-Sum_B作为原本的价格然后用fi,jfi,jf_{i,j}表示已经选了i个人SumA−SumBSumA−SumBSum_A-Sum_B为j时的情况然后用ddd数组统计每个状态是从哪个转移过来的，然后进行dp。注意：c++没有负数下标，所以要加一个m#x00D7;20" role="presentation" style="position: relative;">m×20m×20m\times 20 code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int n,m,f[31][801],a[811],b[811],d[31][801],x,wr[31],t;
bool write(int x,int y,int z)//判断路径是否正确
{while(xd[x][y]!z){y-a[d[x][y]]-b[d[x][y]];x--;}return !x;
}
int main()
{n1;while(scanf(%d%d,n,m)n!0m!0){memset(f,-1,sizeof(f));memset(d,0,sizeof(d));f[0][m*20]0;for(int i1;in;i){scanf(%d%d,a[i],b[i]);}for(int i1;im;i)for(int j0;jm*40;j)if(f[i-1][j]0)//有这个状态for(int k1;kn;k){if(f[i][ja[k]-b[k]]f[i-1][j]a[k]b[k]write(i-1,j,k))//是否可以转移{f[i][ja[k]-b[k]]f[i-1][j]a[k]b[k];d[i][ja[k]-b[k]]k;}}printf(Jury #%d\n,t);int k10;while(k1m*20f[m][m*20k1]0f[m][m*20-k1]0) k1;//寻找答案int ansf[m][m*20k1]f[m][m*20-k1]?m*20k1:m*20-k1;//计算正负printf(Best jury has value %d for prosecution and value %d for defence:\n,(ansf[m][ans]-m*20)1,(f[m][ans]-ansm*20)1);//输出for (int i1,jm,kans;im;i){wr[i]d[j][k];k-a[d[j][k]]-b[d[j][k]];j--;}//记录方案sort(wr1,wr1m);//按顺序for (int i1;im;i) printf( %d,wr[i]);printf(\n\n);}
}
