AOJ 0559: JOI Flag

解法

bitDP(の別解)で解きました.
下から見ていき、Iになっている場所と、直前がJでその下がIという状態を持つことでも解ける.
JOが隣り合う状態を持つ方が状態数が少なくなるが, この解法でもO(n^2*2^n)なのでAOJでは間に合う.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
#define N 20
string g[N];
int dp[2][2][1<<N], mod = 100000;

int main(){
	int h, w;
	cin>>h>>w;
	for(int i = 0; i < h; i++) cin>>g[i];
	int res = 0, f = 0;
	dp[0][0][0] = 1;
	for(int i = h-1; i >= 0; i--){
		for(int j = 0; j < w; j++){
			f ^= 1;
			memset(dp[f], 0, sizeof(dp[f]));
			char c = g[i][j];
			if(c=='?') (res*=3)%=mod;
			for(int k = 0; k < 1<<w; k++){
				int k2 = k&~(1<<j);
				int t1 = dp[!f][0][k], t2 = dp[!f][1][k];
				if(c=='?'||c=='I') (dp[f][0][k2|(1<<j)]+=t1+t2)%=mod;
				if(c=='?'||c=='O'){
					(res += t2)%=mod;
					(dp[f][0][k2]+=t1)%=mod;
				}
				if(c=='?'||c=='J') (dp[f][j<w-1&&((k>>j)&1)][k2]+=t1+t2)%mod;
			}
		}
	}
	cout<<res<<endl;
	return 0;