POJ_1157 LITTLE SHOP OF FLOWERS

問題
解法
動的計画法をつかえば解ける。
詳しくはソース中のコメントみてください。
O(F*V)だからはやい。

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_F = 100, MAX_V = 100, MINF = -(1<<29);
int F, V;
int table[MAX_F + 1][MAX_V + 1];
int dp[MAX_F + 1][MAX_V + 1];
/*
dp[i][j] := 花束i,鉢jまでを使ってできる最大の美しさ
dp[i][j] := max(dp[i][j-1], dp[i-1][j-1] + table[i][j]);
*/
int main(){
	scanf("%d %d", &F, &V);
	for(int i = 1; i <= F; i++)
		for(int j = 1; j <= V; j++)
			scanf("%d", &table[i][j]);
	for(int i = 1; i <= F; i++){
		dp[i][i-1] = MINF;
		for(int j = i; j <= V - F + i; j++){
			dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + table[i][j]);
		}
	}
	printf("%d\n", dp[F][V]);
	return 0;
}