花店橱窗

题意

给 f 朵花，v 个花瓶，每朵花对于每个花瓶都有一个美观值，现在期望美观值最大，让你输出最大的美观值，对于最大的美观值，输出每朵花在花瓶的位置，保证字典序最小。
有一个需要注意的条件是对于每朵花在花瓶的位置，一定大于上一个朵花的位置，也一定小于下一朵花的位置。

题解

首先需要初始化一下结果 dp 数组，让所有的结果都为负数，可能存在一种情况是，有一种花实在是不好看，在每个花瓶中美观值都为负数。

memset(dp, INF, sizeof(dp));

状态转换方程式:

for (int i = 0; i < v; ++ i) {
    dp[0][i] = a[0][i];
}
for (int i = 1; i < f; ++ i) {
    for (int j = 0; j < v; ++ j) {
        for (int k = 0; k < j; ++ k) {
            dp[i][j] = max(dp[i-1][k]+a[i][j], dp[i][j]);
        }
    }
}

回溯一下

    for (int i = 0; i < v; ++ i) {
        if (maxx == dp[f-1][i]) {
            pos = i;
            maxx -= a[f-1][i];
            break;
        }
    }
    res.push_back(pos);
    for (int i = f-2; i >= 0; -- i) {
        for (int j = 0; j < v; ++ j) {
            if (dp[i][j] == maxx) {
                maxx -= a[i][j];
                res.push_back(j);
                break;
            }
        }
    }

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = -0X3f3f3f;
const int maxn = 105;
vector<int> res;
ll dp[maxn][maxn];
int a[maxn][maxn];
int main() {
    memset(dp, INF, sizeof(dp));
    int f, v;
    cin >> f >> v;
    for (int i = 0; i < f; ++ i) {
        for (int j = 0; j < v; ++ j) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < v; ++ i) {
        dp[0][i] = a[0][i];
    }
    for (int i = 1; i < f; ++ i) {
        for (int j = 0; j < v; ++ j) {
            for (int k = 0; k < j; ++ k) {
                dp[i][j] = max(dp[i-1][k]+a[i][j], dp[i][j]);
            }
        }
    }
    ll maxx = 0, pos = 0;
    for (int i = 0; i < v; ++ i) {
        maxx = max(maxx, dp[f-1][i]);
    }

    cout << maxx << endl;
    for (int i = 0; i < v; ++ i) {
        if (maxx == dp[f-1][i]) {
            pos = i;
            maxx -= a[f-1][i];
            break;
        }
    }
    res.push_back(pos);
    for (int i = f-2; i >= 0; -- i) {
        for (int j = 0; j < v; ++ j) {
            if (dp[i][j] == maxx) {
                maxx -= a[i][j];
                res.push_back(j);
                break;
            }
        }
    }

    sort(res.begin(), res.end());
    for (auto x : res) {
        cout << x+1 << " ";
    }
    cout << endl;
    return 0;
}