[每日一题] [NC20242] 最大子矩阵

题目大意：一个最多两列最多100行的数字矩阵，从中选出K个不重叠的矩形，他们的数字之和最大是多少？

https://ac.nowcoder.com/acm/problem/20242

看到最多有两列，可以想到关于每一行的状态进行状态压缩DP，可能状态是：空，左边被占用，右边被占用，左右被不同矩形占用，左右被一个矩形占用。需要维护dp[R][S][N]表示到R行为止处于状态S已经使用N个矩形，最大的和是多少（如果不可能该和为-INF)。状态和个数的转移不难求得，比如dp[5][左右被不同矩形占用][用了5个矩形]可以来自dp[4][空][3], dp[4][左边被占用][4]，等等。

int N,M,K;
int score[105][3];
// dp[row][state][count].
int dp[105][10][20];

#define amax(a,b) a=max(a,b)

#define INF 327670000
// state = 0 <=> nothing
// state = 1 <=> left only
// state = 2 <=> right only
// state = 3 <=> left + right
// state = 4 <=> both
int doit() {
  VVI trans = {
    // state = 0
    {0,0,0,0,0},
    // state = 1
    {1,0,1,0,1},
    // state = 2
    {1,1,0,0,1},
    // state = 3
    {2,1,1,0,2},
    // state = 4
    {1,1,1,1,0},
  };
  FOR(row,0,N){
    for (int state = 0; state <= 4; ++state) {
      for (int cnt = 0; cnt <= K; ++cnt) {
        if(row==0){
          if(state==0&&cnt==0){
            dp[row][state][cnt]=0;
          }else{
            dp[row][state][cnt]=-INF;
          }
        } else {
          dp[row][state][cnt]=-INF;
          int cost = 0;
          if (state==1||state==3||state==4){
            cost+=score[row-1][0];
          }
          if(M==2){
            if (state==2||state==3||state==4){
              cost+=score[row-1][1];
            }
          }
          if (state < 2 || M == 2) {
            for (int prev_state=0;prev_state<=4;++prev_state){
              if(cnt>=trans[state][prev_state]){
                dp[row][state][cnt]=max(dp[row][state][cnt],dp[row-1][prev_state][cnt-trans[state][prev_state]]+cost);
              }
            }
          }
        }
        // print(row,state,cnt,dp[row][state][cnt]);
      }
    }
  }
  int ans = -INF;
  for (int state = 0; state <= 4; ++state) {
    amax(ans,dp[N][state][K]);
  }
  return ans;
}

int main(int argc, char* argv[]) {
  read(N,M,K);
  REP(i,N){
    REP(j,M){
      scanf("%d",&score[i][j]);
    }
  }
  printint(doit());
  return 0;
}