AOJ 2439 Hakone

AOJ

良問DPとして有名な箱根駅伝。結構考えましたがわからず解説を読んでしまいました。
JAGの解説が少しわかりにくかったのでここにまとめておきます。
順位表の'-'は確定するので無視します。
現在の中継地点の順位表を1位から順に見ていって、前の中継地点での順位表を上から埋めていく感じです。
DP[i][j]:=(i位まででj個未確定で放置)の場合の数
というテーブルを考えます。
初期化はdp[0][0]=1で求める値はdp[n][0]です
dp[i][j]からの状態遷移は、

(i)i+1位が'D'の時
1~iで開いてる所(すなわちj個)にi+1位のやつを入れるのでj通り。dp[i+1][j]+=dp[i][j]*j
上とあわせてi+1位のところに放置してたやつ(すなわちj個)を入れるのでj通り。dp[i+1][j-1]+=dp[i][j]*j*j

(ii)i+1位が'U'の時
i+1位のところに放置してたやつ(すなわちj個)を入れるのでj通り。dp[i+1][j]+=dp[i][j]*j
完全に放置。dp[i+1][j+1]+=dp[i][j]

O(N^2)ですが、想定解は未確定の数と放置してたやつ(両者は常に等しい)を分けてO(N^3)のようです

このDPが本当に重複なく数えられているかはdp[0][0]からdp[n][0]までのパスと一対一に対応してることを考えるとわかると思います。

典型と言われるのもわかるような気がします。これの類題は絶対落とさないようにしていく所存です

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
#define MOD 1000000007
ll dp[300][300];
int n;
char c[300];
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)cin >> c[i];
	dp[0][0]=1ll;
	for(int i=0;i<n;i++)
	{
		if(c[i]=='-')for(int j=0;j<=n;j++)dp[i+1][j]=dp[i][j];
		if(c[i]=='D')
		{
			for(int j=0;j<=i;j++)
			{
				if(j>0)dp[i+1][j-1] = (dp[i+1][j-1]+(((dp[i][j]*j)%MOD)*j%MOD))%MOD;
				dp[i+1][j] = (dp[i+1][j]+((dp[i][j]*j)%MOD))%MOD;
			}
		}
		if(c[i]=='U')
		{
			for(int j=0;j<=i;j++)
			{
				dp[i+1][j+1] = (dp[i+1][j+1]+dp[i][j])%MOD;
				dp[i+1][j] = (dp[i+1][j]+((dp[i][j]*j)%MOD))%MOD;
			}
		}
	}
	printf("%lld\n",dp[n][0]);
	return 0;
}