D. Recovering BST Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)

时间：2021-10-08 06:57:52

http://codeforces.com/contest/1025/problem/D

树 dp 优化

　　f[x][y][0]=f[x][z][1] & f[z+1][y][0] ( gcd(a[x-1],a[z])<>0 )

　　f[x][y][1]=f[x][z][1] & f[z+1][y][0] ( gcd(a[z],a[y+1])<>0 )

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <time.h>

 #include <string>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <vector>

 #include <bitset>

 #include <ext/rope>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 #define ll long long

 #define minv 1e-6

 #define inf 1e9

 #define pi 3.1415926536

 #define E  2.7182818284

 const ll mod=1e9+;//

 const int maxn=1e3+;

 int a[maxn];

 bool vis[maxn][maxn]={},f[maxn][maxn][]={};

 int main()

 {

     int n,i,j,x,y,z;

     scanf("%d",&n);

     for (i=;i<=n;i++)

         scanf("%d",&a[i]);

     for (i=;i<n;i++)

         for (j=i+;j<=n;j++)

             vis[i][j]=(__gcd(a[i],a[j])!=);

     for (i=;i<=n;i++)

         vis[][i]=,vis[i][n+]=;

     for (i=;i<=n+;i++)

         f[i][i-][]=f[i][i-][]=;

     for (i=;i<=n;i++)

         for (x=,y=i;x<=n-i+;x++,y++)

             for (z=x;z<=y;z++)

                 if (f[x][z-][] && f[z+][y][])

                 {

                     if (vis[x-][z])

                         f[x][y][]=;

                     if (vis[z][y+])

                         f[x][y][]=;

                 }

     if (f[][n][])

         printf("Yes");

     else

         printf("No");

     return ;

 }

相关文章