http://acm.pku.edu.cn/JudgeOnline/problem?id=1837
#include<iostream>
using namespace std;
#define MAX 10000
#define base 5000
#define hmax 21
int m[hmax][MAX];
int h[hmax],w[hmax];
int c,g;
/**//*
m[i,j]表示前i个位置 得到力矩为j的方案的 数目
m[i][j]=Σm[i-1,j-w[i]*h[k]] i砝码数 k位置
base避免负数
*/
int main()
{
while(scanf("%d%d",&c,&g)!=EOF){
for(int i=0;i<c;++i)scanf("%d",&h[i]);
for(int i=0;i<g;++i)scanf("%d",&w[i]);
memset(m,0,sizeof(m));
for(int i=0;i<c;++i)++m[0][w[0]*h[i]+base];
for(int i=1;i<g;++i)
for( int j=-base;j<=base;++j){
int tmp=0;
for( int k=0;k<c;++k)
if( m[i-1][base+j-h[k]*w[i]])tmp+=m[i-1][base+j-h[k]*w[i]];
m[i][base+j]=tmp;
}
printf("%d\n",m[g-1][base]);
}
return 0;
}
继续幼稚地保留代码，并贴出出来。
posted on 2009-03-17 20:43
爬 阅读(1282)
评论(0) 编辑 收藏 引用 所属分类:
Dynamic programming