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個(gè)位置 得到力矩為j的方案的 數(shù)目
m[i][j]=Σm[i-1,j-w[i]*h[k]] i砝碼數(shù) k位置
base避免負(fù)數(shù)
*/
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;
}
繼續(xù)幼稚地保留代碼，并貼出出來(lái)。
posted on 2009-03-17 20:43
爬 閱讀(1304)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Dynamic programming