随笔 - 26  文章 - 6  trackbacks - 0
<2009年9月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

常用链接

留言簿(3)

随笔分类

随笔档案

朋友

  • cqh
  • 大学室友...

搜索

  •  

最新评论

阅读排行榜

评论排行榜

#include <iostream>
#define MAX 22
using namespace std;

const int mm = 8000;

int dp[MAX][mm+mm];
int arm[MAX], w[MAX];


/*
dp[i][mm+k]:取前i个时,天平处于k状态的方法数
      mm+k:    < mm为左边重, > mm 为右边重 
dp[i][mm+k] += 
            dp[i-1][mm + k-weight[i]*arm[j]], (j:1->c)};   
*/


int main()
{
    
int c, g, i, j, k;
    
while(cin >> c >> g){
        
for(i = 0; i < c; i++)
            cin 
>> arm[i];
        
for(i = 0; i < g; i++)
            cin 
>> w[i];

        memset(dp, 
0sizeof(dp));
        
for(j = 0; j < c; j++)
            dp[
0][mm + arm[j]*w[0]] = 1;
        
for(i = 1; i < g; i++){
            
for(k = -mm; k <= mm; k++){
                
int sum = 0;
                
for(j = 0; j < c; j++)
                    
if(k - arm[j]*w[i] >= -mm && k - arm[j]*w[i] <= mm)
                    sum 
+= dp[i-1][mm + k - arm[j]*w[i]];
                dp[i][mm
+k] = sum; 
            }

        }

        cout 
<< dp[g-1][mm] << endl;
    }

return 0;
}

posted on 2009-05-15 09:53 longshen 阅读(483) 评论(0)  编辑 收藏 引用 所属分类: poj

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