プログラム設計思考と実践Week 16模擬試合C宇宙犬の危機

タイトルの説明:
瑞神大戦宇宙線の中で私たちは宇宙犬のすごいところを知った.宇宙犬は凶悪だが、宇宙犬にはかわいい彼女がいる.最近、彼の彼女はいくつかの数を得て、同時に、彼女はまたとても木が好きで、だから彼女は得た数を1粒の木につづるつもりです.この日、彼女はもうすぐ試合が終わると同時に、友达と休暇を約束して遊びに行きました.食いしん坊の宇宙犬はうっかり木の枝を全部食べてしまった.だから恐怖は宇宙犬を包囲し、彼は今木全体を回復しようとしているが、この木が二叉探索木であることを知っているだけで、任意の木のそばにつながっている2つのノードのgcd(greatest common divisor)は1を超えている.しかし、宇宙犬は宇宙線を発射するだけで、彼はあなたの助けを求めて、あなたにこの問題を解決することができるかどうかを聞いています.
input:
データ・グループ数を表す最初の行のtを入力します.データのセットごとに、最初の行にnを入力し、数の個数を表す次の行にn個の数$a_を入力します.i$、入力保証は昇順です.
output:
データのセットごとに1行ずつ出力し,問題記述を満たすツリーを作成できればYesを出力し,そうでなければNoを出力する.
考え方:
正解区間dp,試験時に採用される暴力検索:ルートノードの位置を列挙し,ルートノードの左側の区間に左サブツリーの根を見つけ,ルートノードの右側に右サブツリーの根を見つけて再帰する.ある点の左右の子樹が見つかると,その点を根とする木が成り立つ.暴力アルゴリズムはO(n!)で、枝を切った後の時間の複雑さはやや小さい.40点を取った.
区間dp:メンテナンス状態f[i][j]は、1表示区間i~jであれば1本の二叉探索木を構成することができ、0であれば二叉探索木を形成できないことを示す.サブ区間
f[i][k]とf[k][j]はいずれも二叉探索ツリーを構成できるが,区間が連続的に増加するため,二つの区間が結合してkをルートノードとする二叉探索ツリーが形成される.第1層の循環列挙区間長は、0~n-1(区間長が0の場合は1点のみ、区間長がn-1の場合は全区間)となる.そして列挙区間の開始位置を開始し、区間長に応じて区間の終了位置を得る.最後に列挙区間におけるルートノードを列挙する.

#include
#include
#include
using namespace std;
int T,n,a[1010];
bool f[1010][1010],flag[1010][1010];
bool l[1010][1010],r[1010][1010];
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main()
{
	cin>>T;
	while(T--)
	{
		memset(f,0,sizeof f);
		memset(l,0,sizeof l);
		memset(r,0,sizeof r);
		memset(flag,0,sizeof flag);		
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			l[i][i]=r[i][i]=1;
		}
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		if(i==j) continue;
		else if(gcd(a[i],a[j])>1)
		flag[i][j]=true;
		for(int len=0;len