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]) 이런 상황은 아무것도 선택하지 않는 것을 대표한다.
l[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가 두 줄을 차지하는 사각형(이 행렬의 길이는 0이 될 수 있다)을 일일이 열거할 수 있다. 그러면 w[i][k]=max(w[j][k]+f[j+1][ii]+sum[ii][ii]]]]][ii]]]]를 대표한다.이 이동은 먼저 한 번의 단점을 열거한 다음에 한 개의 단점을 i로 열거하는 경우이다. 한 줄만 선택한 다음에 한 줄이 두 줄의 최대치를 차지한다. 그러면 먼저 한 줄의 f[i][j][k]값을 처리해야 한다. 이것은 i를 대표하고 j단은 k개 행렬의 최대치를 선택한다.나중에 이동할 때 매거 경계가 너무 번거로워서 조정하지 못했다. 다시 생각해 보니 이런 이동은 상태수가 너무 적어서 모든 상태를 정확하게 표현할 수 없기 때문에 옮기는 것이 매우 번거롭다. 그래서 1차원을 더하면 모든 상태를 정확하게 표현할 수 있고 옮기는 것이 매우 편리하다. 복잡도도 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[0][1]=sum[0][2]=0;

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

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

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

    if (m==1){

        memset(f,0,sizeof(f));

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

            f[i][0]=0;

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

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

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

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

                }

            }

        }

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

    } else {

        memset(w,0,sizeof(w));

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

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

                w[i][j][0]=0;

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

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

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

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

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

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

                    if (i==j)

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

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

                }

            }       

        }

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

    }

    return 0;

}