SGU 104 Little shop of flowers【DP】

波(食べる)一日、水道の问题は冷静で冷静です....
タイトルリンク:
http://acm.sgu.ru/problem.php?contest=0&problem=104
タイトル:
各花を各植木鉢に置く値を指定して、番号の大きい花は番号の小さい花の後ろに置くしかなくて、各花はすべて植木鉢の中に置いて、どのように置いて総額を最大にすることができますか?
分析:
やはり水のdpを比較して...各位置には2つの状況があります:放すか放さないか.置かないとdp[i][j−1][0]は前の最近の植木鉢が置かれた値に等しい.放すと、dp[i][j][1]が更新されます.これにより、各植木鉢i花jに対して、max(dp[i−1][j−1][0],dp[i−1][j−1][1])がj−1番花を置いた後に得られる最大の値を示すことが保証される.最後に逆押ししてパスを取得すればいいです.
コード:

#include<cstdio>
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
const int maxn = 100 + 5;
int dp[maxn][maxn][2];
int v[maxn][maxn];
stack<int>s;
int main (void)
{
    int n, m;
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &v[i][j]);
        }
    }
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0][0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j - 1][0] = max(dp[i - 1][j - 1][0] ,dp[i - 1][j - 1][1]);
            dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + v[j][i];
        }
    }
    int ans = max(dp[n][m][1], dp[n][m][0]);
    printf("%d
", ans);
    int sta = n;
     for(int i = m; i >= 0; i--){
        for(int j = sta; j >= 0; j--){
            if(dp[j][i][1] == ans && ans){
                s.push(j);
                sta = j - 1;
                ans -= v[i][j];
                break;
            }
        }
    }
    while(!s.empty()){
        int res =s.top();
        s.pop();
        printf("%d ", res);
    }
    printf("
");
    return 0;
}