Codeforces Round #14 E.Camels

問題概要

(x1,y1),(x2,y2),...,(xn,yn)を順に結んだ折れ線がある。
x1=1,x2=2,...,xn=nであり、1≦yi≦4で、各座標は全て整数である。
またすべての折れ線の部分はx軸に平行にはならない。

n,tが与えられるとき、このような折れ線のうち、

• 山（yj-1 < yj > yj+1） がt個
• 谷（yj-1 > yj < yj+1） がt-1個

あるものは何通りあるかを求めよ。

n≦20,t≦10である。

解法

折れ線を全てシミュレートする（3^n）のはおそらくTLE.
場合の数の問題の定石通りに動的計画法を用いる。

最新の2つのy座標および、山、谷の数をメモする動的計画法ならば数十msで解ける。
以下のコードでは、
dp[x座標+1][山の数][谷の数][一つ前のy座標][y座標]にその段階までの場合の数を記憶している。

ソースコード

int dp[20][11][10][4][4];

void run()
{
	int n,t; cin>>n>>t;
	rep(i,n)rep(u,11)rep(d,10)rep(j,4)rep(k,4)dp[i][u][d][j][k]=0;
	rep(i,4)rep(j,4)if(i!=j)dp[1][0][0][i][j]=1;
	
	for(int i=2;i<n;i++)
	rep(j,4)rep(k,4)rep(l,4)if(k!=l)
	rep(u,i/2+2)rep(d,i/2+2)
	{
		
		dp[i][u+(j<k&&k>l)][d+(j>k&&k<l)][k][l]+=
		dp[i-1][u][d][j][k];
	}
	
	int ans=0;
	rep(j,4)rep(k,4)ans+=dp[n-1][t][t-1][j][k];
	cout<<ans<<endl;
}