P1854 花店橱窗布置 解题笔记

思路：

我们用一个二维数组 \(dp[i][j]\) 来表示第 \(i\) 束花放不放在第 \(j\) 个花瓶中的最大值，此时，我们可以进行以下两个操作：

• 不放，状态可以描述为：\(dp[i][j] = dp[i][j - 1]\)。
• 放，状态可以描述为：\(dp[i][j] = dp[i - 1][j - 1] + a[i][j]\)。

由于题目还要求求方案，所以我们用一个数组保存转移路径，从前往后回溯得到答案。

中途出现的错误：

1. 美学值可能为负数，在初始化 \(dp\) 数组时未将它的值改为负数。
2. 在求出最大美学值后用 dfs 来求方案，导致超时。
3. 求解过程中为判重花瓶，导致好几束花插在了一个花瓶里。

code：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1009][1009],b[1009][1009],c[1009][1009],e[1009];
int main()
{cin>>n>>m;for(int i=0;i<=m;i++){b[0][i]=0;}for(int i=1;i<=n;i++){long long mx=0,d=0;for(int j=1;j<=m;j++){cin>>a[i][j];b[i][j]+=a[i][j]+50;if(b[i][j]>=mx)d=j;mx=max(b[i][j],mx);b[i+1][j+1]=mx;c[i+1][j+1]=d;}if(i==n){cout<<mx-50*n<<endl;for(int j=n;j>=1;j--){e[j]=d;d=c[j][d];}for(int j=1;j<=n;j++){cout<<e[j]<<" ";}}}
}