Joyoi花店橱窗（原tyvj1124）

题目：http://www.joyoi.cn/problem/tyvj-1124

两点注意！！！

1.滚动数组的初始化；

2.字典序操作！

感到很有趣！！！

#include<iostream>

#include<cstdio>

using namespace std;

const int INF=-0x7fffffff;

int n,m,pos[][],pre[][],ans[];

long long a[][],d[][],mx=INF;

int main()

{

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

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

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

            scanf("%lld",&a[i][j]);

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

    {

        if(a[][i]>mx)

        {

            mx=a[][i];

            pos[][i]=i;

        }

        else pos[][i]=pos[][i-];

        d[][i]=mx;

    }

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

    {

        d[i%][i-]=INF;//////因为是滚动数组，故初始化memset INF有漏洞 ,且i+1的时候不会用到这里了，可放心

        for(int j=i;j<=m-(n-i);j++)

        {

            if(d[i%][j-]>=d[(i-)%][j-]+a[i][j])//////字典序

            {

                d[i%][j]=d[i%][j-];

                pos[i][j]=pos[i][j-];

                pre[i][j]=pre[i][j-];

            }

            else

            {

                d[i%][j]=d[(i-)%][j-]+a[i][j];

                pos[i][j]=j;

                pre[i][j]=pos[i-][j-];

            }

        }

    }

    printf("%lld\n",d[n%][m]);

    int k=pos[n][m];

    for(int i=n;i;i--)

    {

//        while(a[i][k-1]==a[i][k])k--;//////字典序 (不行！会过头……)

        ans[i]=k;

        k=pre[i][k];

    }

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

        printf("%d ",ans[i]);

    return ;

}