poj1837

/* solution: 背包型dp dp[i][j]表示选到第i个时，平衡度为j的方法数. 转移方程：dp[i][j+C[k]*G[i]] += dp[i][j]; note: 1：注意初始条件的初始化 2：关于该题目中平衡度，因为在极端条件下，左右两边的极限值为：20*25*15=7500 所以极限值范围：-7500～+7500;有由于下标不能为负数，所以将平衡值从0移动为7500 这样平衡值范围为0～15000.从一个状态转移到另外一个状态，平衡值变化j+C[k]*G[i]。 便很容易得到状态转移方程。 date: 2016.8.16 */ #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 20 + 5; int c, g; //c是钩子数量，g是砝码数量 int C[maxn], G[maxn]; int dp[maxn][15000]; //dp[i][j]表示选到第i个时，平衡度为j的方法数 int main() { //freopen("input.txt", "r", stdin); while(~scanf("%d%d", &c, &g)) { for(int i = 1; i <= c; i++) scanf("%d", &C[i]); for(int j = 1; j <= g; j++) scanf("%d", &G[j]); memset(dp, 0, sizeof(dp)); dp[0][7500] = 1; //什么都不放就是一种方案 //cout << "#\n"; //dp[i][j+C[k]*G[i]] += dp[i][j]; for(int i = 1; i <= g; i++) { for(int j = 0; j <= 15000; j++) { if(dp[i-1][j]) { for(int k = 1; k <= c; k++) { dp[i][j+C[k]*G[i]] += dp[i-1][j]; } } } } cout << dp[g][7500] << endl; } return 0; }