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 << " "; } }
题解汇总 文章被收录于专栏
无