POJ 1837 Balance(二维DP)

题目描述

总结

1. 偏移的设置又思考了很久, 实际上, 枚举几个例子就能把思路找出来

2. dp[i][j], 循环的最外两层循环分别是 i, j

3. 初始化问题, dp[i][j] 初始化成 0 更好, 下面的代码写的很丑, 就是因为初始化没搞好. 做题时若实在拿捏不准到底初始化成 0, 1 还是 INF, 那就都试试

代码

/*
 * source.cpp
 *
 *  Created on: Apr 5, 2014
 *      Author: sangs
 */

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <memory.h>
using namespace std;

const int INF = 0X80808080;
int dp[30][20000];
int pos[1000];
int weight[1000];

int cal(int n, int m) {
	memset(dp, 0x80, sizeof(dp));
	dp[0][7500] = 1;

	for(int i = 1; i <= m; i ++) { // enum weight
		for(int j = 0; j <= 15000; j ++) {  // enum balance value
			for(int k = 1; k <= n; k ++) { // enum position

				if(dp[i-1][j] == INF) continue;

				int newBalance = (pos[k]*weight[i]) + j;
				if(dp[i][newBalance] == INF) {
					dp[i][newBalance]  = dp[i-1][j];
				}else {
					dp[i][newBalance] += dp[i-1][j];
				}

				//printf("dp[%d][%d] = %d
", i, newBalance-7500, dp[i][newBalance]);
			}
		}
	}
	if(dp[m][7500] == INF)
		return 0;
	return dp[m][7500];
}

int main() {
	freopen("input.txt", "r", stdin);
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF) {
		for(int i = 1; i <= n; i ++)
			scanf("%d", pos+i);
		for(int i = 1; i <= m; i ++)
			scanf("%d", weight+i);

		int res = cal(n, m);
		printf("%d
", res);
	}
	return 0;
}