5E02 花店櫥窗?0x5E「動態規劃」練習

背景

xq和他的老婆xz最近開了一家花店，他們準備把店里最好看的花都擺在櫥窗里。但是他們有很多花瓶，每個花瓶都具有各自的特點，因此，當各個花瓶中放入不同的花束時，會產生不同的美學效果。為了使櫥窗里的花擺放的最合適，他們得想個辦法安排每種花的擺放位置。
可是因為xq和xz每天都太忙，沒有時間設計櫥窗里花的擺法，所以他們想讓你幫他們求出花擺放的最大美觀程度和每種花所放的位置。

描述

? ? 每種花都有一個標識，假設杜鵑花的標識數為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，表示xq和xz一共有F種花，V個花瓶。(1<=F<=V<=100)
第2行到第F+1行：每行有V個數，表示花擺放在不同花瓶里的美觀程度值value。(美觀程度和不超過maxint，美觀程度有正有負)

?

輸出格式

輸出有兩行：第一行為輸出最大美觀程度和的值，第二行有F個數表示每朵花應該擺放的花瓶的編號。若有多種方案，輸出字典序較小的（美觀程度不變的情況下，花盡量往前放）

樣例輸入

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

樣例輸出

53 2 4 5

題意：

有f種花，v個花瓶。每種花放在不同的花瓶得到的beauty值是不同的，給出這個價值矩陣。擺放花的順序不可以改變，即花的序號是遞增的。現在問一個方案，使得beauty之和是最大的。輸出方案。

思路：

原來的思路是 用dp[i][j]表示前j個花瓶擺了i種花，用j作為階段。但是這樣好像不是很好輸出路徑。

應該用dp[i][j]表示第i種花放在第j個花瓶。然后枚舉k，表示第i-1種花放在第k個花瓶。

1 //#include <bits/stdc++.h> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<stdio.h> 6 #include<cstring> 7 #include<vector> 8 #include<map> 9 10 #define inf 0x3f3f3f3f 11 using namespace std; 12 typedef long long LL; 13 14 int f, v; 15 int val[105][105], dp[105][105], path[105][105], res[105]; 16 17 18 int main() 19 { 20 scanf("%d%d", &f, &v); 21 for(int i = 1; i <= f; i++){ 22 for(int j = 1; j <= v; j++){ 23 scanf("%d", &val[i][j]); 24 } 25 } 26 27 memset(dp, -inf, sizeof(dp)); 28 for(int i = 1; i <= v; i++){ 29 dp[1][i] = val[1][i]; 30 } 31 for(int i = 2; i <= f; i++){ 32 for(int j = i; j <= v - (f - i); j++){ 33 for(int k = i - 1; k < j; k++){ 34 if(dp[i - 1][k] > dp[i][j]){ 35 dp[i][j] = dp[i - 1][k]; 36 path[i][j] = k; 37 } 38 } 39 dp[i][j] += val[i][j]; 40 } 41 } 42 43 int pos, ans = -inf; 44 for(int i = v - f; i <= v; i++){ 45 if(dp[f][i] > ans){ 46 ans = dp[f][i]; 47 pos = i; 48 } 49 } 50 printf("%d\n", ans); 51 res[f] = pos; 52 for(int i = f - 1; i >= 1; i--){ 53 res[i] = path[i + 1][res[i + 1]]; 54 } 55 printf("%d", res[1]); 56 for(int i = 2; i <= f; i++){ 57 printf(" %d", res[i]); 58 } 59 printf("\n"); 60 return 0; 61 }

?

轉載于:https://www.cnblogs.com/wyboooo/p/9767209.html

總結

以上是生活随笔為你收集整理的CH5E02 花店橱窗【线性DP】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。