POJ 1157 LITTLE SHOP OF FLOWERS

题意:给出F朵花,V个花瓶,每朵花插入每个花瓶都有一个美观值,要求第i朵花所在的花瓶号小于第j朵花所在的花瓶号(i < j), 求最大的累计美观值.

设dp[i][j]为前i朵花插入到前j个花瓶能得到的最大美观值(i <= j)

则

如果i == 1,dp[i][j] = max(dp[i][j - 1], val[i][j])

否则如果j > V - F + i(i能插的地方只能在[i, V - F + i]号花瓶里,所以):dp[i][j] = dp[i][j - 1]

否则:dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + val[i][j]) dp[i][j - 1]为第i多花不插到第j个花瓶里能带来的美观值,dp[i - 1][j - 1]为前i - 1朵花插在j - 1个花瓶里的最大美观值加上第i朵花插在第j个花瓶里的美观值.

初始化所有dp[i][j]为负无穷( 1<= i <= F, 0 <= j <= V ).

#include <algorithm>
#include <memory.h>
#include <cstdio>
#define NINF -100000000
using namespace std;
const int MAX = 102;

int dp[MAX][MAX];
int val[MAX][MAX];

int main(int argc, char const *argv[]){
	int F, V;
	while(scanf("%d%d", &F, &V) == 2){
		for(int i = 1; i <= F; ++i){
			dp[i][0] = NINF;
			for(int j = 1; j <= V; ++j){
				scanf("%d", &val[i][j]);
				dp[i][j] = NINF;
			}
		}
		for(int i = 1; i <= F; ++i){
			for(int j = i; j <= V; ++j){
				if(j > V - F + i){
					dp[i][j] = dp[i][j - 1];
				}else{
					if(i == 1){
						dp[i][j] = max(dp[i][j - 1], val[i][j]);
					}else{
						dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + val[i][j]);
					}
				}
			}
		}
		printf("%d\n", dp[F][V]);
	}
	return 0;
}

POJ 1157 LITTLE SHOP OF FLOWERS,布布扣,bubuko.com

POJ 1157 LITTLE SHOP OF FLOWERS

原文：http://blog.csdn.net/zxjcarrot/article/details/21295995