[題解]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[][];

int f[][],g[][];

inline void print(int i,int k)

{

    if(!i)return ;

    print(i-,g[i][k]);

    printf("%d ",k);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    scanf("%d",&w[i][j]);

    for(int i=;i<=m;i++)f[][i]=w[][i];

    for(int i=;i<=n;i++)//第i朵花

    for(int j=i;j<=m;j++)//第j個花瓶

    for(int k=i-;k<=j-;k++){//從前面k狀態轉移

        if(f[i][j]<f[i-][k]+w[i][j]){

            f[i][j]=f[i-][k]+w[i][j];

            g[i][j]=k;

        }

    }

    int ans=,ansi;

    for(int i=n;i<=m;i++){

        if(ans<f[n][i])

        ans=f[n][i],ansi=i;

    }

    printf("%d\n",ans);

    print(n,ansi);

}

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

PS.自然可以壓掉 i 維

巴特西

[題解]luogu_P1854 花店櫥窗佈置

最新文章

热门文章