Codeforces Round #117 (Div. 2) E : Wooden Fence

問題概要(適当)

板をあるルールに従って並べる。並べ方が何通りあるか求める問題。

解法

素直に(長さ、最後に使った板のタイプ、最後に使った板は縦か横か)を状態としてdpする。計算量結構怪しいけど間に合う。
…というのがwriterも引っかかった間違いで、これだとタイプ列として見たとき同じだけど縦横の使われ方が違う、というのを重複して数えてしまう。多分この問題だと効率的に解くのは難しく、実際この問題のせいでunratedになった。

acceptされたコード

計算量O(L*N^2)。

#include <cstdio>
using namespace std;

typedef long long int64;

const int64 MOD = (int64)(1e9 + 7);
const int MAX_L = 3000;
const int MAX_N = 100;

int N, L;
int as[MAX_N][2];
int64 dp[MAX_L + 1][MAX_N][2];

void init(){
	scanf("%d%d", &N, &L);
	for(int i=0; i<N; ++i){
		scanf("%d%d", as[i]+0, as[i]+1);
	}
}

int solve(){

	for(int i=0; i<N; ++i){
		for(int j=0; j<2; ++j)if(j == 0 || (as[i][0] != as[i][1])){
			++dp[as[i][j]][i][j^1];
		}
	}

	for(int l=0; l<L; ++l){
		for(int i=0; i<N; ++i){
			for(int j=0; j<2; ++j){
				for(int k=0; k<N; ++k)if(i!=k){
					for(int p=0; p<2; ++p)if( p == 0 || (as[k][0] != as[k][1])){
						if(l + as[k][p] <= L && as[i][j] == as[k][p]){
							dp[l+as[k][p]][k][p^1] += dp[l][i][j];
							if(dp[l+as[k][p]][k][p^1] >= MOD){
								dp[l+as[k][p]][k][p^1] -= MOD;
							}
						}
					}
				}
			}
		}
	}

	int64 ans = 0;
	for(int i=0; i<N; ++i){
		for(int j=0; j<2; ++j){
			ans = ( ans + dp[L][i][j] ) % MOD;
		}
	}

	return (int)ans;
}

int main(){
	init();
	printf("%d\n", solve());

	return 0;
}