POJ1157解题报告

题目链接： 

思路：一道dp题目，还是蛮有意思的。

如果花瓶数量和花的数量一样，那么只有一种插花的方法；

如果花瓶数大于花的数量，那么就考察最后一个花瓶是否插花，可以归结为两个相应的最优子问题。

具体的状态方程如下：

用state[V][F]记录状态， V是瓶子的数量，F是花的数量。

state[i][j] = state[i-1][j-1] + value[i][j]  if i == j

state[i][j] = max { state[i-1][j-1] + value[i][j], state[i][j-1] }  if i < j

#include 
#include 

using namespace std;

#define MAX 101

class Solution {
	public:
		void run() {
			while (cin >> flowerNum >> vaseNum) {
				for (int i=1; i<=flowerNum; i++)
					for (int j=1; j<=vaseNum; j++)
						cin >> value[i][j];
				cout << dp() << endl;
			}
		}
	private:
		int dp() {
			int pre = 0, cur;
			memset(state[pre], 0, sizeof(int)*MAX);
			
			for (int i=1; i<=flowerNum; i++) {
				cur = i%2;
				pre = (i + 1) % 2;
				state[cur][i] = state[pre][i-1] + value[i][i];
				for (int j=i+1; j<=vaseNum; j++) {
					if (state[pre][j-1] + value[i][j] > state[cur][j-1])
						state[cur][j] = state[pre][j-1] + value[i][j];
					else
						state[cur][j] = state[cur][j-1];
				}
			}
			return state[cur][vaseNum];
		}

		int vaseNum;
		int flowerNum;
		int state[2][MAX];
		int value[MAX][MAX];
};

int main() {
	Solution solution;
	solution.run();

	return 0;
}