首页 > 分享 > 花店橱窗（线性dp）

花店橱窗（线性dp）

花匠小妙招
2024-12-10 07:16

花店橱窗

小q和他的老婆小z最近开了一家花店，他们准备把店里最好看的花都摆在橱窗里。

但是他们有很多花瓶，每个花瓶都具有各自的特点，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果。

为了使橱窗里的花摆放的最合适，他们得想个办法安排每种花的摆放位置。

可是因为小q和小z每天都太忙，没有时间设计橱窗里花的摆法，所以他们想让你帮他们求出花摆放的最大美观程度和每种花所放的位置。

每种花都有一个标识，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：

杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。

如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。

每种花放在不同的瓶子里会产生不同的美观程度，美观程度可能是正数也可能是负数。

上述例子中，花瓶与花束的不同搭配所具有的美观程度，如下表所示：

花瓶 1 2 3 4 5 1 (杜鹃花) 7 23 -5 -24 16 2 (秋海棠) 5 21 -4 10 23 3 (康乃馨) -21 5 -4 -20 20

根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得十分难看。

为取得最大美观程度，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值，并求出每种花应该摆放的花瓶的编号。

输入描述:

第1行：两个整数F和V，表示共有F种花，V个花瓶。
第2行到第F+1行：每行有V个数，表示花摆放在不同花瓶里的美观程度值value。(美观程度和小于2^{31}，美观程度有正有负)

输出描述:

输出有两行：第一行为输出最大美观程度和的值，第二行有F个数表示每朵花应该摆放的花瓶的编号。
若有多种方案，输出字典序较小的方案（美观程度不变的情况下，花尽量往前放）。

示例1

输入

3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20

输出

备注:

1≤F≤V≤100

题目思路

这题真坑，有三个地方要注意。
dp[i][j]表示摆了i种花，且第i种花的位置在j的最大值,location[i][j]表示第i种花摆在j时上一种花摆在哪。
1.因为可能有负数，所以dp要初始化为负无穷，dp[0][0] = 0为边界
2.第i种花的位置必须要大于第i-1种花，所以j的范围要注意，要从i-1开始，到m-(n-i)结束
3.第三个循环的k表示上一种花的位置，这里k要升序循环，因为答案要求按照字典序，这里坑了我好久

代码如下

#include<bits/stdc++.h> #define ll long long using namespace std; ll n,m,a[101][101],dp[101][101],ans,location[101][101],x; void locat(ll n,ll x) { if(n==1) cout<<x<<" "; else { locat(n-1,location[n][x]); cout<<x<<" "; } } int main() { memset(dp,128,sizeof(dp));//可能有负数，所以设为无穷大 ans = -1000000001; cin>>n>>m; for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) cin>>a[i][j]; dp[0][0] = 0;//边界 for(int i = 1;i<=n;i++) for(int j = i;j<=m-(n-i);j++)//位置在j，这里j的范围要搞清 for(int k = i-1;k<=j-1;k++)//上一种花的位置,这里应该从小到大，因为要按照字典序 if(dp[i-1][k]+a[i][j]>dp[i][j]) { dp[i][j] = dp[i-1][k]+a[i][j]; location[i][j] = k; } for(int i = n;i<=m;i++) { if(dp[n][i]>ans) { ans = dp[n][i]; x = i; } } cout<<ans<<endl; locat(n,x); return 0; }