NC51216 花店橱窗

记录一个坑点，不能用注释里的代码求最大值，因为如果n多花放完价值和为负数，但n-1朵放完价值和为正数，那么ans保留的就是n-1朵的答案

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 105;
int arr[maxn][maxn];
long long dp[maxn][maxn];
vector<int>res;
int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = -0x3f3f3f3f;
        }
    }
    long long ans = -0x3f3f3f3f;
    for (int i = 1; i <= m; i++) {
        dp[1][i] = arr[1][i];
    }
    for (int i = 2; i <= n; i++) {
        for (int j = i; j <= m; j++) {
            for (int k = 1; k < j; k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + arr[i][j]);
            }
            // ans = max(ans, dp[i][j]);
        }
    }
    for (int i = 1; i <= m; i++) {
        ans = max(ans, dp[n][i]);
    }
    cout << ans << endl;
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            if (dp[i][j] == ans) {
                res.push_back(j);
                ans -= arr[i][j];;
                break;
            }
        }
   }
    sort(res.begin(), res.end());
    for (auto i : res) {
        if (i != 0)
            cout << i << " ";
    }
}