题解 P1854 【花店橱窗布置】

· · 题解

这题dp大水题，但还是卡了我好久

其实可以将其看成一个以花为横，瓶为纵的表格

从下向上找一条路径，上一排的位置必须小于下一排

大家可以看我注释掉的调试码来观察我的心路历程

应为是找路径嘛，所以肯定要需要上一层的数据来状态转移

这个时候我们就不能外层循环花瓶数而内层循环花束了

应为那样子只有上一列数据而没有上一层数据

所以dp的循环层数也是有讲究的！！！

大家在推出状态转移方程的时候也必须要考虑当前状态转移需要用到的数据上层有没有提供！！！

这也是初始化的意义所在

关于dp的边界，当大家不懂的时候可以自己一个一个去尝试

有的时候去掉等于号啊，或者m，n打错了啊会造成不可逆的结果

所以这道题给我的经验就是

状态的转移必须依赖上一层数据到底有没有

请打表验证

如果没有，请手动模拟后

初始化，改变循环顺序或循环边界

希望大家能有所学习借鉴

#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
int a[105][105],f[105][105],pos[105][105],ans[105];
int n,m;
int main(){
    scanf("%d%d",&n,&m);                 //n朵花，m个瓶子 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)            //f[i][j]前i束里放了前j个瓶子 
            scanf("%d",&a[i][j]);        //a[i][j]第i朵花放在第j个瓶子内的美学值 
    for(int j=1;j<=m;j++)                  
        f[1][j]=a[1][j];

/*

    for(int i=2;i<=m;i++){               //i个瓶子 
        for(int j=1;j<=n;j++){           //j朵花   注意要从i开始！！并且还要给后面的留位置 
            for(int k=i-1;k<j;k++){        //这一层是要循环上一朵花瓶子的的位置 
                if(f[i][j]<f[k][j-1]+a[i][j]){    //在这里必须要空出前面的位置和给后面留位置 
                    f[i][j]=f[k][j-1]+a[i][j];       
                    pos[i][j]=k;         //在i，j的最优解中上一束花的存放位置 
                }
            }   
        }
    }
    */                        //       这都是不行的！！！！ 
    for(int i=1;i<=n;++i)
     for(int j=1;j<=m;++j)
      f[i][j]=-777666555;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=m-n+i;j++){
            for(int k=i-1;k<j;k++){
                if(f[i][j]<f[i-1][k]+a[i][j]){
                    f[i][j]=f[i-1][k]+a[i][j];
                    pos[i][j]=k;
                }
            }
        }
    } 
/*    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<f[i][j]<<"  ";
        cout<<endl;
    }

*/

    int maxl=-1;
    int k;                               //k代表当前位置 
    for(int j=1;j<=m;j++)
      if(maxl<f[n][j]){
          maxl=f[n][j];
          k=j;
      }
//    cout<<maxl<<"   "<<k;
    printf("%d\n",maxl);
    for(int i=n;i>=1;i--){
        ans[i]=k;
        k=pos[i][k];
    }
    for(int i=1;i<=n;i++)
         printf("%d ",ans[i]); 
    return 0;
}