bzoj 1084 DP

　　首先对于m==1的情况非常容易处理（其实这儿因为边界我错了好久。。。），直接DP就好了，设f[i][k]为这个矩阵前i个选k个矩阵的最大和，那么f[i][k]=max(f[j][k-1]+sum[j+1][i])，那么对于m==2的时候类似与m=1的时候，设w[i][j][k]为左面的一行前i个中，右面的一行前j个中，一共选k个矩阵能选取得最大矩阵。

　　那么转移也比较明显，有一下几种转移

　　w[i][j][k]=max(w[i-1][j][k],w[i][j-1][k])这种情况代表什么都不选。

　　w[i][j][k]=max(w[ii][j][k-1]+sum[ii+1][i][0])这种情况代表在左面一行重新确定i这个位置如何选取。

　　类似的w[i][j][k]=max(w[i][jj][k-1]+sum[jj+1][j][1])这种情况代表在右面一行重新确定i这个位置如何选取。

　　当i==j的时候w[i][j]=max(w[ii][ii]+sum[ii+1][i][2])，这样就代表选了一个占两行的矩形，然后注意枚举的边界就可以了。

　　反思：开始我的想法是w[i][k]代表两行矩阵前i个选k个矩阵的最大值，我们可以知道选取矩阵的方法肯定是若干段只选取一行的组合，然后由选取两行的隔开，那么我们可以枚举i代表在i出选取占两行的矩形（这个矩形的长可以为0），那么w[i][k]=max(w[j][k]+f[j+1][ii]+sum[ii][i])，这个转移就是先枚举上一次的断点，然后后枚举上一断点到i的情况，就是一段只选取一行的加上一个占两行的最大值，那么首先要处理每一行的f[i][j][k]值，代表i,j段选取k个矩阵的最大值。后来因为转移的时候枚举边界特别麻烦，没有调出来，再仔细想想之后发现这种转移由于状态数太少，没办法准确的表达每一个状态，所以转移起来非常麻烦，所以就加了一维，可以准确的表达所有状态，而且转移十分方便，复杂度也降低了一个k（因为上一种方法需要枚举左右两行各选多少矩形），总之，还是自己太弱了。。。

/**************************************************************

    Problem: 1084

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:88 ms

    Memory:1672 kb

****************************************************************/

//By BLADEVIL

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 100

#define maxm 20

using namespace std;

int n,m,k;

int a[maxn][maxn],sum[maxn][maxn],f[maxn][maxm],w[maxn][maxn][maxm];

int main(){

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

    sum[][]=sum[][]=;

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

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

            scanf("%d",&a[i][j]),sum[i][j]=sum[i-][j]+a[i][j];

    if (m==){

        memset(f,,sizeof(f));

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

            f[i][]=;

            for (int l=;l<=k;l++){

                f[i][l]=f[i-][l];

                for (int j=;j<i;j++){

                    f[i][l]=max(f[i][l],f[j][l-]+sum[i][]-sum[j][]);

                }

            }

        }

        printf("%d\n",f[n][k]);

    } else {

        memset(w,,sizeof(w));

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

            for (int j=;j<=n;j++){

                w[i][j][]=;

                for (int l=;l<=k;l++){

                    w[i][j][l]=max(w[i-][j][l],w[i][j-][l]);

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

                        w[i][j][l]=max(w[i][j][l],w[ii][j][l-]+sum[i][]-sum[ii][]);

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

                        w[i][j][l]=max(w[i][j][l],w[i][jj][l-]+sum[j][]-sum[jj][]);

                    if (i==j)

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

                            w[i][i][l]=max(w[i][i][l],w[jj][jj][l-]+sum[i][]-sum[jj][]+sum[j][]-sum[jj][]);

                }

            }

        }

        printf("%d\n",w[n][n][k]);

    }

    return ;

}

巴特西

bzoj 1084 DP

最新文章

热门文章