Codefes2015 Final G

本番で解けなかった問題。区間DP。

解説だと「区間を木にできるかだと4乗になって、区間を森にできるかどうかを考えると3乗に落ちる」と言われていましたが、「区間を木にできるかどうか」だけで3乗にできます。

まず、

DP[区間][一番最後の子x]: 区間の左端を根として、その根の最後の(一番右の)直接の子がxであるようなもの

というDPを考えます。このままだと4乗になります。一番最後の子というのは、そのあとさらに区間の左端のノード(この区間の根ノード)に子となる木が生やせるかどうかを判定するために使います。

しかし、この区間で木を作るとき、その左端のノードに新たに木を子として生やすならば、その生やす木の根は、この区間の直後のノードです。

ということは、一番最後の子が何かというのを覚えておく必要はなくて、一番最後の子の番号が区間の直後のノードの番号より大きいかどうかだけを覚えておけばいいことになります。

ということで、状態数がO(N^2)、遷移は合わせてO(N^3)のDPになりました。めでたしめでたし。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod=1000000007;
ll dp[256][256][2];
int main()
{
	int num;
	scanf("%d",&num);
	vector<int>vec;
	for(int i=0;i<num;i++)
	{
		int zan;
		scanf("%d",&zan);
		vec.push_back(zan);
	}
	vec.push_back(1000000000);
	if(vec[0]!=1)
	{
		printf("0\n");
		return 0;
	}
	for(int i=0;i<num;i++)dp[i][i][0]=1;
	for(int d=2;d<=num;d++)
	{
		for(int i=0;i<num;i++)
		{
			int j=i+d-1;
			if(j>=num)break;
			for(int k=i;k<=j-1;k++)
			{
				if(vec[k+1]<vec[j+1])
				{
					dp[i][j][0]+=dp[i][k][0]*dp[k+1][j][0];
					dp[i][j][0]+=dp[i][k][0]*dp[k+1][j][1];
					dp[i][j][0]%=mod;
				}
				else
				{
					dp[i][j][1]+=dp[i][k][0]*dp[k+1][j][0];
					dp[i][j][1]+=dp[i][k][0]*dp[k+1][j][1];
					dp[i][j][1]%=mod;
				}
			}
		}
	}
	printf("%lld\n",(dp[0][num-1][0]+dp[0][num-1][1])%mod);
}