随笔-20  评论-16  文章-36  trackbacks-0
      这题乍一看很像搜索,可是暴搜要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 古月残辉 阅读(2114) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理