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 
#include 
#include 
#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;
}