题解 P1854 花店橱窗布置

for(R i=1;i<=n;i++) 
    for(R j=V-(n-i);j>=i;j--) 
        for(R k=j-1;k>=i-1;k--) 
            if(f[i][j]<f[i-1][k]+w[i][j])
                ans[i][j]=k,f[i][j]=f[i-1][k]+w[i][j];

for(R i=1;i<=n;i++) for(R j=V-(n-i);j>=i;j--) {
        f[j]=0xcfcfcfcf;
        for(R k=j-1;k>=i-1;k--) if(f[j]<f[k]+w[i][j]) ans[i][j]=k,f[j]=f[k]+w[i][j];
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define R register int
using namespace std;
int n,V,pos=109;
int w[110][110],f[110][110],ans[110][110];

inline void print(int i,int j) {
    if(!i) return ;
    print(i-1,ans[i][j]);
    printf("%d ",j);
}

signed main() {
//freopen("testdata.in","r",stdin);
    memset(f,0xcf,sizeof(f));
    scanf("%d%d",&n,&V);f[n][109]=0xcfcfcfcf;
    for(R i=1;i<=n;i++) for(R j=1;j<=V;j++) scanf("%d",&w[i][j]); 
    for(R i=0;i<=V;i++) f[0][i]=0;
    for(R i=1;i<=n;i++) for(R j=V-(n-i);j>=i;j--) 
        for(R k=j-1;k>=i-1;k--) if(f[i][j]<f[i-1][k]+w[i][j]) ans[i][j]=k,f[i][j]=f[i-1][k]+w[i][j];//,cout<<i<<" "<<j<<" "<<k<<" "<<f[1][1]<<endl;
    for(R i=V;i>=n;i--) if(f[n][i]>f[n][pos]) pos=i;
    printf("%d\n",f[n][pos]),print(n,pos);
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define R register int
using namespace std;
int n,V,pos=109;
int w[110][110],f[110],ans[110][110];

inline void print(int i,int j) {
    if(!i) return ;
    print(i-1,ans[i][j]);
    printf("%d ",j);
}

signed main() {
    //freopen("testdata.in","r",stdin);
    //memset(f,0xcf,sizeof(f));
    scanf("%d%d",&n,&V);f[109]=0xcfcfcfcf;
    for(R i=1;i<=n;i++) for(R j=1;j<=V;j++) scanf("%d",&w[i][j]); 
    //for(R i=0;i<=V;i++) f[0][i]=0;
    for(R i=1;i<=n;i++) for(R j=V-(n-i);j>=i;j--) {
        f[j]=0xcfcfcfcf;
        for(R k=j-1;k>=i-1;k--) if(f[j]<f[k]+w[i][j]) ans[i][j]=k,f[j]=f[k]+w[i][j];//,cout<<i<<" "<<j<<" "<<k<<" "<<f[1][1]<<endl; 
    }
    for(R i=V;i>=n;i--) if(f[i]>f[pos]) pos=i;
    printf("%d\n",f[pos]),print(n,pos);
}