bitDP。面倒な形してるよね。
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int len[128]; int dp[2][1<<16]; char str[128][17]; int L[16][1<<16]; int R[16][1<<16]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%s",str[i]); len[i]=strlen(str[i]); } for(int i=0;i<b;i++){ for(int j=0;j<(1<<b);j++){ for(int k=0;k<b;k++) if(j&(1<<k)){ if(k<i)L[i][j]++; else R[i][j]++; } } } int u=0; int mask=(1<<b)-1; int inf=99999999; for(int i=1;i<(1<<b);i++)dp[u][i]=-inf; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ for(int k=0;k<(1<<b);k++)dp[!u][k]=-inf; for(int k=0;k<(1<<b);k++){ if(len[i]<L[j][k])continue; if(len[i]>L[j][k]+b-j)continue; if(len[i]>L[j][k]){ int A=0; if(j&&(k&1)&&(str[i][L[j][k]]==str[i][L[j][k]-1]))A++; if(i&&(k&(1<<b-1))&&(str[i-1][len[i-1]-R[j][k]]==str[i][L[j][k]]))A++; dp[!u][(k*2+1)&mask]=max(dp[!u][(k*2+1)&mask],dp[u][k]+A); } if(len[i]<L[j][k]+b-j){ dp[!u][(k*2)&mask]=max(dp[!u][(k*2)&mask],dp[u][k]); } } u=!u; } } int ret=0; for(int i=0;i<(1<<b);i++) ret=max(ret,dp[u][i]); printf("%d\n",ret*2); } /* INTERNATIONAL C O LLEGIATE PROGRAMMING C O NTEST */