这题乍一看很像搜索，可是暴搜要20^20，无法接受，看了Discuss可以用DP，再想想觉得的确很巧妙~~
用l[i]表示第i个点的x坐标值，用w[i]表示第i个砝码的重量，用opt[i][j]表示加了i个砝码，两边力矩之差为j的可能方法数，则本题只要计算出opt[i][0]，即最终力矩差为0的方法数即可。由于质量差可能为负，这里加上一个偏移量，考虑原题的数据可知，要想平衡，则一边力矩至多为15*25*10=3750，故每个j加上3750。
状态转移方程：opt[i+1][k+w[i]*l[j]]+= opt[i][k]，i=0~g，j=0~c，k=0~7500
输出结果：opt[w][3750]
下面是实现代码：
#include <iostream>
using namespace std;
int main()
{
int i, j, k, l[21], w[21], opt[21][7501], c, g;
scanf("%d%d",&c,&g);
for( i= 0; i< c; i++ )
scanf("%d",&l[i]);
for( i= 0; i< g; i++ )
scanf("%d",&w[i]);
memset(opt,0,sizeof(opt));
for( i= 0; i< c; i++ )
opt[1][l[i]*w[0]+3750]++;
for( i= 1; i< g; i++ )
for( j= 0; j< c; j++ )
for( k= 0; k<= 7500; k++ )
if( opt[i][k] )
opt[i+1][k+w[i]*l[j]]+= opt[i][k];
printf("%d\n",opt[g][3750]);
return 0;
}
PS：1745 Divisibility这题也是用了加偏移的DP，那道题还有一个亮点，就是%k的使用……不知道这是不是传说中的滚动数组~~
posted on 2009-06-20 21:38
古月残辉 阅读(2116)
评论(0) 编辑 收藏 引用 所属分类:
POJ