poj 1837 Balance -- 动态规划

#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, 0, sizeof(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 阅读(482) 评论(0) 编辑收藏引用所属分类: poj

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: poj 3254 Corn Fields -- 状态压缩DP poj 1947 Rebuilding Roads -- 树形DP poj 1837 Balance -- 动态规划 poj 2192 Zipper -- 简单DP poj 2186 Popular Cows -- 强连通分支 poj 2762 Going from u to v or from v to u? -- 强连通 poj 1191 棋盘分割 -- 动态规划

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

随笔分类