AOJ : 2449
問題リンク:Connect | Aizu Online Judge
問題概要:
略
解法:
1行覚えるタイプの動的計画法
dp[r][c][bit] := (c,r)までで使用する文字列の状態がbitの時の最大値
としてDPする
bitの数を数えてその行の文字列よりも多く使用する場合などはcontinueする
2重ループで次に文字を置く場所を決める
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; }