题解 P1854 【花店橱窗布置】

· · 题解

题解挺多的，我就负责再提供一个，竞争优势就是负号合成的测试数据……

/*3 5 7 23 -5 -24 16

5 21 -4 10 23

-21 5 -4 -20 20*/

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[120][120],f[120][120];
void dg(int i,int j)
{
    int n;
    if (i>0)
    {
        n=i;
        while (f[i][n]!=j)
          n++;
        dg(i-1,j-a[i][n]);
        printf("%d ",n);
     } 
}
int main()
{
    int ff,n,i,j,k;
    scanf("%d%d",&ff,&n);
    for (i=1;i<=ff;i++)
      for (j=1;j<=n;j++)
        scanf("%d",&a[i][j]);    
    f[1][1]=a[1][1];
    for (j=2;j<=n;j++)    
      f[1][j]=max(a[1][j],f[1][j-1]);
    for (i=2;i<=ff;i++)//f[i][j]表示前i束花插在前j个瓶子里的最大美学值
      for (j=i;j<=n-ff+i;j++)
        for (k=i;k<=j;k++)
          f[i][j]=max(f[i-1][k-1]+a[i][k],f[i][j]);
    printf("%d\n",f[ff][n]);
    dg(ff,f[ff][n]);
}