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