AOJ : 2449

問題リンク:Connect | Aizu Online Judge

問題概要:
略

解法:
１行覚えるタイプの動的計画法
dp[r][c][bit] := (c,r)までで使用する文字列の状態がbitの時の最大値
としてDPする
bitの数を数えてその行の文字列よりも多く使用する場合などはcontinueする
２重ループで次に文字を置く場所を決める
bits_Lは置く場所(c,r)の左にあるビットの数で、ビットは置く場所の左に置いてある文字列の状態を表す
bits_Rは置く場所の上からその右にあるビットの数で、ビットはその場所の文字列の状態を表す

メモ：

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)

using namespace std;

int R,C,dp[2][(1<<16)],len[130];
string s[130];
int bitcount[(1<<16)];

int main(){

  cin >> R >> C;
  rep(i,R){
    cin >> s[i];
    len[i] = (int)s[i].size();
  }

  rep(i,(1<<C))bitcount[i] = __builtin_popcount(i);
  rep(i,(1<<C))dp[0][i] = -1;
  dp[0][0] = 0;

  int answer = 0;
  rep(r,R)rep(c,C){

    int phase = ( (c+r*C) & 1 );
    int next_phase = !phase;

    rep(i,(1<<C))dp[next_phase][i] = -1;

    rep(state,(1<<C)){
      if( dp[phase][state] == -1 ) continue;
      int next_state = state & (~(1<<c));
      int bitmask = (1<<c)-1;
      int bits_L = bitcount[bitmask&state];//__builtin_popcount(bitmask&state);
      int bits_R = bitcount[state]-bits_L;//__builtin_popcount(state)-bits_L;


      //明らかにbitの数がおかしいときはcontinue
      if( ( r-1 >= 0 && bits_R > len[r-1] ) || ( r-1>=0 && c+bits_R < len[r-1] ) ) continue; 
      if( bits_L > len[r] || ( C-c+bits_L < len[r] ) ) continue;

      //(c,r)になにも置かない
      dp[next_phase][next_state] = max(dp[next_phase][next_state],dp[phase][state]);
      answer = max(answer,dp[next_phase][next_state]);

      next_state |= (1<<c);
      int score = 0;
      char char_M = s[r][bits_L]; 
      if( r-1 >= 0 && bits_R <= len[r-1] && c+bits_R >= len[r-1] ){ // (c,r-1)
	if( bits_R > 0 && ((state>>c)&1) ){
	  char char_R = s[r-1][len[r-1]-bits_R];
	  if( char_M == char_R ) score++;
	}
      }

      if( c-1 >= 0 && bits_L < len[r] && C-c+bits_L >= len[r] ){   // (c-1,r)
	if( bits_L > 0 && ((state>>(c-1))&1) ){
	  char char_L = s[r][bits_L-1];
	  if( char_L == char_M ) score++;
	}
      }

      dp[next_phase][next_state] = max(dp[next_phase][next_state],dp[phase][state]+score);
      answer = max(answer,dp[next_phase][next_state]);

    }
  }
  cout << answer*2 << endl;

  return 0;
}