首页 > 分享 > 动态规划 luogu P1854 花店橱窗布置

动态规划 luogu P1854 花店橱窗布置

花匠小妙招
2024-09-15 07:30

题目大意

P1854
给你 n n n束花和 m m m个花瓶，第 i i i束花放在第 j j j个花瓶中可以取得 a i , j a_{i,j} ai,j的好看值，并且第 i i i束花必须放在第 i + 1 i+1 i+1束花左边。每个花瓶仅能放一束花，花瓶的数量可能大于花的数量，求出最大可以获得多少好看值以及第 i i i朵花应该放到哪一个花瓶中。

题目描述

首先我们来处理最大好看值。当看到第 i i i束花必须放在第 i + 1 i+1 i+1束花左边时，就应该想到dp的无后效性。定义dp数组 f f f， f i , j f_{i,j} fi,j表示前 i i i束花放在前 j j j个花瓶时能获得的最大好看值，我们这时只需要考虑第 i i i束花需不需要放在第 j j j个花瓶里，若是放，则 f i , j = f i − 1 , j − 1 + a i , j f_{i,j}=f_{i-1,j-1}+a_{i,j} fi,j=fi−1,j−1+ai,j，即前 i − 1 i-1 i−1束花放在前 j − 1 j-1 j−1个花瓶里得到的最大值加上当前第 i i i束花放在第 j j j个花瓶时的值。若是不放，则 f i , j = f i , j − 1 f_{i,j}=f_{i,j-1} fi,j=fi,j−1。
再考虑放的花瓶的位置，位置其实在处理好看值时就可以顺便求出来，因为第 f i , j f_{i,j} fi,j已经是当前 i i i束花放在前 j j j个花瓶里时可获得的最大好看值了，所以只需要记录得到 f i , j f_{i,j} fi,j时放的花瓶的位置即可。因此定义一个结构体 w w w， w . i , j w._{i,j} w.i,j中的 a a a数组即为前 i i i束花放在前 j j j个花瓶时每个放了花的花瓶的位置。

代码

#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; struct ap{int a[110],l;//l为放了花的花瓶的数量 }w[110][110]; int a[110][110],f[110][110],n,m; int main() {ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];memset(f,-127,sizeof(f));for(int i=0;i<=m;i++)f[0][i]=0;for(int i=1;i<=n;i++)for(int j=i;j<=m;j++){if(f[i-1][j-1]+a[i][j]>f[i][j-1]){w[i][j]=w[i-1][j-1];w[i][j].a[++w[i][j].l]=j;//多放置一个花瓶f[i][j]=f[i-1][j-1]+a[i][j];}else{w[i][j]=w[i][j-1];//不放f[i][j]=f[i][j-1];}}cout<<f[n][m]<<endl;for(int i=1;i<=w[n][m].l;i++)cout<<w[n][m].a[i]<<" ";//输出最后的方案return 0; }

1234567891011121314151617181920212223242526272829303132333435363738