首页分享洛谷 P1854 花店橱窗布置(算法竞赛进阶指南，线性DP)

洛谷 P1854 花店橱窗布置(算法竞赛进阶指南，线性DP)

来源：花匠小妙招时间：2024-11-14 17:31

算法竞赛进阶指南347页，线性DP
题目：
每一排选一个数，求一个最大的和，要求前一排选的数比后一排选的数靠左。
本题要点：
1、状态表示：
dp[i][j] 表示前 i朵花，放入前j个花盆中，获得最大值。
vis[i][j] = true, 如果 dp[i - 1][j - 1] + mp[i][j] > dp[i][j - 1]
2、状态转移
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + mp[i][j]);
3、输出方案：
每一行从右往左找，找到第一个 vis[i][j] 为true的，则为第i行选的该数j，再从第i-1一行的j-1向左找，直到找出所有

#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MaxN = 110; int n, m; int mp[MaxN][MaxN]; int dp[MaxN][MaxN]; bool vis[MaxN][MaxN];//vis[i][j] = true, 如果 dp[i - 1][j - 1] + mp[i][j] > dp[i][j - 1] int ans[MaxN]; void solve() {memset(vis, false, sizeof vis);memset(dp, 0x80, sizeof dp);for(int i = 0; i <= m; ++i)dp[0][i] = 0;for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + mp[i][j]);if(dp[i - 1][j - 1] + mp[i][j] > dp[i][j - 1]){vis[i][j] = true;}}}int k = m;for(int i = n; i >= 1; --i){for(; k >= 1; --k){if(vis[i][k]){ans[i] = k--;break;}}}printf("%dn", dp[n][m]);for(int i = 1; i <= n; ++i){printf("%d", ans[i]);if(i < n){printf(" ");}else{printf("n");}} } int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)scanf("%d", &mp[i][j]);solve();return 0; } /* 3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20 */ /* 53 2 4 5 */

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374