P1854 花店橱窗布置 题解

#include <bits/stdc++.h>

using namespace std;

int f, v;

int a[110][110];

int dp[110][110];//第i朵花放在第j个花瓶的最优解

void print(int x, int y) {

if (x > 0) {

int n = x;

//若现在有x朵花，就从第x个位置开始枚举到哪一个的美观度是等于y

while (dp[x][n] != y) {

n++;

}

//如果枚举到了，那么就去枚举x-1朵花，他的美观度是y-a[x][n];

print(x - 1, y - a[x][n]);

printf("%d ", n);

}

}

int main() {

cin >> f >> v;

for (int i = 1; i <= f; i++) {

for (int j = 1; j <= v; j++) {

cin >> a[i][j];

}

}

for (int i = 1; i <= f; i++) {

for (int j = i; j <= v; j++) {

dp[i][j] = -0x7f;

for (int k = i - 1; k <= j - 1; k++) {

dp[i][j] = max(dp[i - 1][k] + a[i][j], dp[i][j]);

}

}

}

int ans = -0x7f;

for (int i = f; i <= v; i++) {

ans = max(ans, dp[f][i]);

}

cout << ans << endl;

print(f, ans);

}

第i朵花放在第j个位子时，所能达到的最大值

dp[ i ][ j ] = max(dp[ i-1 ][ k ])+a[ i ][ j ]  k=i-1,i-2,i-3.......j-1

相关知识

P1854 花店橱窗布置 题解
[动态规划]花店橱窗布置
[Tyvj 1124]花店橱窗布置
花店橱窗怎么设计？吸引人的花店橱窗要怎么布置？
【DP】花店橱窗布置
花店橱窗陈列的花卉最好是本花店的()。
春季花店这样布置，生意爆好！
[线性dp]花店橱窗 AcWing313
花店外部的灯光设计要怎么布置？
婚庆铁艺艺花路引仿真婚礼布置绢花主桌橱窗婚庆绢花

网址: P1854 花店橱窗布置 题解 https://www.huajiangbk.com/newsview117870.html