SGU 104 Little shop of flowers

可愛的DP，應該要可以快速解決

dp[i][j] = the biggest aes-value when there are i bunch flowers and j vases

dp[i][j] = min{ dp[i-1][k] + aes[i][j] }

//By momo
#include<cstdio>
#include<algorithm>
#define N 110
#define INF 999999999
using namespace std;

int dp[N][N], f, v, a[N][N], pv[N][N], pnt[N], pn;

int main(){
    scanf("%d%d", &f, &v);
    for(int i = 1; i <= f; i++) for(int j = 1; j <= v; j++) dp[i][j] = -INF;
    for(int i = 1; i <= f; i++) for(int j = 1; j <= v; j++) scanf("%d", &a[i][j]);
    for(int i = 1; i <= f; i++) for(int j = 1; j <= v; j++){
        if(f == 1){ dp[i][j] = a[i][j], pv[i][j] = -1; continue; }
        for(int k = 1; k < j; k++){
            if(dp[i][j] < dp[i-1][k]+a[i][j]){
                dp[i][j] = dp[i-1][k]+a[i][j];
                pv[i][j] = k;
            }
        }
    }
    int ans = -INF, x;
    for(int i = 1; i <= v; i++){
        if(ans < dp[f][i]){
            ans = dp[f][i];
            x = i;
        }
    }
    printf("%d\n", ans);
    for(int i = f; i > 0; x = pv[i--][x]) pnt[pn++] = x;
    while(pn--) printf("%d%c", pnt[pn], pn == 0?'\n':' ');
}