首页分享【DP】花店布置

【DP】花店布置

来源：花匠小妙招时间：2026-04-26 01:07

最新推荐文章于 2025-06-07 17:40:19 发布

原创于 2021-05-14 09:20:41 发布 · 226 阅读

· 0

· 1 ·

CC 4.0 BY-SA版权

小目录题目描述样例输入样例输出思路代码

题目描述

现有n朵花， m 个花盆，每朵花在不同花盆里有不同的美观度，而且花与花之间的安放有一定顺序，现在求所有花都按照顺序放进花盆后，可以获得的最大美观度是多少

样例输入

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

样例输出

53 1

思路

初一欠到现在终于补掉的题
DP
设 f i , j f_{i,j} fi,j表示到第i个花盆时放到第j朵花的最大美观

第i盆不放花 f i , j = m a x ( f i , j , f i − 1 , j ) f_{i,j} = max(f_{i,j}, f_{i-1, j}) fi,j=max(fi,j,fi−1,j)第i盆放花 f i , j = m a x ( f i , j , f k , j − 1 + a i , j ) f_{i,j} = max(f_{i,j}, f_{k, j - 1} + a_{i,j}) fi,j=max(fi,j,fk,j−1+ai,j)(枚举上一盆花放哪收益最大)

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int m, n, a[105][105], f[105][105]; int main() {freopen("flower.in", "r", stdin);freopen("flower.out", "w", stdout);memset(f, -0x3f, sizeof(f));//美观度可能是负数，所以要设初始化为一个很大的负数scanf("%d%d", &m, &n);for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j)scanf("%d", &a[i][j]);f[0][0] = 0;for(int i = 1; i <= m; ++i)f[i][i] = f[i - 1][i - 1] + a[i][i];//前m盆，每一个花盆都放花for(int i = 1; i <= n; ++i)//枚举花盆for(int j = 1; j <= min(m, i); ++j)//花盆充足最多放m朵花，不充足最多放i朵{f[i][j] = max(f[i][j], f[i - 1][j]);for(int k = j - 1; k < i; ++k)//要按照顺序排放f[i][j] = max(f[i][j], f[k][j - 1] + a[j][i]);}printf("%d", f[n][m]);return 0; }

cpp

12345678910111213141516171819202122232425262728293031