题解 P1854 【花店橱窗布置】

niiick · 2017-12-09 13:25:57 · 题解

我们把题目的数据像题面那样用表格列出来就会发现， 其实题意简化后就是

给定一个f*v的矩阵

要求从第一行走到第f行，每行取走一个数，

且该行所取的数必须必上一行所取的数的列数大 ， 求所能取走的最大值

注意每一行所取走的数字的列数必须大于等该行的行号

因为必须给前面的花留下足够的花瓶

同理每一行所能取的最大的花瓶号必须小于等于v-(f-该行行数)

由此我们便可以很容易的得出状态转移方程

其中dp[i][j]表示从第一行走到第i行并取走该行第j个数所能取得的最大值

for(int i=1;i<=v-f;i++) 
dp[1][i]=d[1][i];
//第一朵花所能获得的最大美学值都赋值为本身
//注意边界i<=v-f

for(int i=2;i<=f;i++)
for(int j=i;j<=v-f+i;j++)//注意j<=v-f+i
for(int k=1;k<j;k++)//枚举上一行中最大的dp值
if(dp[i-1][k]+d[i][j]>dp[i][j])
dp[i][j]=dp[i-1][k]+d[i][j];

接下来就是方案输出的问题了

设pre[i][j]表示能让dp[i][j]最大的上一行的花瓶号 , 只要在状态转移过程中更新即可

//niiick
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=1010;
int f,v;
int d[maxn][maxn];
int dp[maxn][maxn],pre[maxn][maxn];

void print(int x,int y)
{
    if(pre[x][y]==y){ printf("%d ",y);  return;}
    print(x-1,pre[x][y]);
    printf("%d ",y);
}

int main()
{
    f=read();v=read();

    for(int i=1;i<=f;i++)
    for(int j=1;j<=v;j++)
    d[i][j]=read();

    for(int i=1;i<=v-f;i++) 
    dp[1][i]=d[1][i],pre[1][i]=i;;
    //第一朵花所能获得的最大美学值都赋值为本身
    //注意边界i<=v-f

    for(int i=2;i<=f;i++)
    for(int j=i;j<=v-f+i;j++)//注意j<=v-f+i
    for(int k=1;k<j;k++)//枚举上一行中最大的dp值
    if(dp[i-1][k]+d[i][j]>dp[i][j])
    {
        dp[i][j]=dp[i-1][k]+d[i][j];
        pre[i][j]=k;
    }

    int tx=f,ty,ans=0;
    for(int i=f;i<=v;i++)
    if(dp[f][i]>ans){ ans=dp[f][i]; ty=i;}

    printf("%d\n",ans);
    print(tx,ty);
    return 0;
}