题解 P1854 【花店橱窗布置】

· · 题解

我们可以用f[i][j]来记录第i株花放在j位置时的美学值

因为第一种花必定在第二种花之前（也就是无后效性）

所以可以通过i-1盆花的状态推出来i盆花的最佳位置

注意一下每一层循环的边界条件我们可知以下的状态转移方程

for(int i=1;i<=n;++i)
 for(int j=i;j<=m-n+i;++j)//因为后面还有花要放所以时(i，m-n+i)
  for(int k=i-1;k<j;++k)
   f[i][j]=max(f[i][j],f[i-1][k]+v[i][j])

然后就是要处理每株花存放的位置

我们可以建立一个数组pre[i][j]来存当这一株花放在(i,j)时上一株花的位置

那么最后我们对f[n][i]找最大的时候，同时也可以知道最后一株花的位置

这时我们可以通过倒推找到每一株花的位置，整个问题就解决了

#include<cstdio>
#include<algorithm>
using namespace std;
int v[105][105],f[105][105];
int pre[105][105],p[105];
int n,m,ans;
int main()
{
    scanf("%d%d",&n,&m);//因为f,v重名了就继续用n,m了 
    for(int i=1;i<=n;++i)
     for(int j=1;j<=m;++j)
      scanf("%d",&v[i][j]);

    for(int i=1;i<=n;++i)
     for(int j=1;j<=m;++j)
      f[i][j]=-1000000;//init

    for(int i=1;i<=n;++i)
     for(int j=i;j<=m-n+i;++j)//因为后面还有花要放所以时(i，m-n+i)
      for(int k=i-1;k<j;++k)
       if(f[i][j]<f[i-1][k]+v[i][j])
        f[i][j]=f[i-1][k]+v[i][j],pre[i][j]=k;//只要更新那么目前上一层最佳位置就是k 

    for(int i=n;i<=m;++i)
     if(ans<f[n][i])
      ans=f[n][i],p[n]=i;
      //最后一个的位置已经找到 
    printf("%d\n",ans);
    for(int i=n;pre[i][p[i]];i--)
     p[i-1]=pre[i][p[i]];
     //通过下一层的pre找到该层位置,不存在的时候就停止 
    for(int i=1;i<=n;++i)
    printf("%d ",p[i]);
    return 0;
}