Week16 CSP模拟 宇宙狗的危机

问题描述：

思路解析：

1.区间dp，l[i][j]表示以j为根,j的左子树可到i 这样的BST是否存在，r[i][j]表示以i为根,i的右子树可到j 这样的BST是否存在，区间[i,j]合法,当且仅当l[i][k]&r[k][j]==1。
2.c[i][j]表示区间[i,j]合法，即a[i~j]可以组成BST，即l[i][k]&r[k][j]=1，k为[i,j]的根。
3.如果区间[L,R]合法且以K为根，则c[L][R]=1。若此时g[K][L-1]=1（即根K和L-1可以相连），则根K可以作为L-1的右孩子（因为L-1<K）,即r[L-1][R]=1；同理，若g[K][R+1]=1，则根K可以作为R+1的左孩子，即l[L][R+1]=1。
4.最后c[1][n]就是能否构成BST的答案。

总结：这道题目自己没有考虑出来，参考了其他人的解法。有动态规划朦胧的感觉，但不知道如何下手。在考场上骗分忘记输出No。。。

代码实现：

#include <iostream>
using namespace std;

int t,n;
const int maxn=1000;
int a[maxn];
int g[maxn][maxn],l[maxn][maxn],r[maxn][maxn],c[maxn][maxn];
int gcd(int a,int b){return b==0 ? a : gcd(b,a%b);}
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
			    c[i][j]=0;
				l[i][j]=0;
				r[i][j]=0;
				g[i][j]=gcd(a[i],a[j]);
				if(g[i][j]==1)
					g[i][j]=0;
				else
					g[i][j]=1;

			}
		for(int i=1;i<=n;i++)
        {
            l[i][i]=1;
            r[i][i]=1;
        }
		int R;
		for(int len=1;len<=n;len++)
		{
			for(int L=1,R=L+len-1;R<=n;L++,R++)
			{
				for(int K=L;K<=R;K++)
				{
					if(l[L][K]&&r[K][R])
					{
						c[L][R]=1;
						if(g[K][L-1])
							r[L-1][R]=1;
						if(g[K][R+1])
							l[L][R+1]=1;
					}
				}
			}
		}
		if(c[1][n])
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
}