[題解]luogu_P1854 花店櫥窗佈置

來源：題解

---

一開始看不懂題目，一萬年了終於看懂

f [ i ] [ j ] 表示第i朵花放在第j個花瓶中最大美學值，（花是必須用完嗎?）

顯然放i-1朵花至少要放到前i-1個瓶子里，最多放到前j-1個瓶子里（因為這個要放到第j個瓶子）

所以就遍歷一下 （i-1，j-1）這個區間轉移一下

f [ i ] [ j ]=max( f [ i ] [ j ] , f [ i-1 ] [ k ]+w[ i ] [ j ] ) ( i-1<=k<=j-1 )

輸出方案只要選擇 g [ i ] [ j ]記錄f [ i ] [ j ]放到了哪個瓶子，然後遞歸輸出，應該是比較常用的，

千萬注意最後可行的答案在 f [ n ] [ n ] ~ f [ n ] [ m ]都有可能，要找一個最大的（類似于->過河）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,w[101][101];
int f[101][101],g[101][101];
inline void print(int i,int k)
{
    if(!i)return ;
    print(i-1,g[i][k]);
    printf("%d ",k);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&w[i][j]);
    
    for(int i=1;i<=m;i++)f[1][i]=w[1][i];
    
    for(int i=2;i<=n;i++)//第i朵花 
    for(int j=i;j<=m;j++)//第j個花瓶
    for(int k=i-1;k<=j-1;k++){//從前面k狀態轉移 
        if(f[i][j]<f[i-1][k]+w[i][j]){
            f[i][j]=f[i-1][k]+w[i][j];
            g[i][j]=k;
        }
    }
    int ans=0,ansi;
    for(int i=n;i<=m;i++){
        if(ans<f[n][i])
        ans=f[n][i],ansi=i;
    }
    printf("%d
",ans);
    print(n,ansi);
}

題目明明說的輸出 f 行每行兩個數啊，為什麼這樣輸出就可以？？？

PS.自然可以壓掉 i 維