D. Recovering BST Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
2024-10-18 22:36:44
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 ;
}
最新文章
- iOS开发小技巧--微博项目中的键盘工具条
- django创建blog
- 《大道至简》第一章读后感--JAVA语言伪代码形式
- 明白何谓Margin Collapse
- js数量添加(如购物车添加,删减数量)
- Cassandra + Eclipse + Hadoop
- EasyUI datagrid添加右键菜单项
- 【viewport】移动设备的兼容性问题
- [转]Django时间查询
- 利用PowerDesigner15在win7系统下对MySQL 进行反向工程(一)
- FileReader对象的readAsDataURL方法来读取图像文件
- JdbcTemplate实体映射
- 【转】嵌入式系统 Boot Loader 技术内幕,带你完全了解Boot Loader
- 如何修改DEDECMS文章标题长度
- 配置Codeblocks
- XE7 &; FMX 那些年我们一起上过的控件:ListView 之 (3) 加载数据时如何显示自定义样式
- ajax和promise的结合使用
- LOCAL_WHOLE_STATIC_LIBRARIES与LOCAL_STATIC_LIBRARIES的区别
- java多线程 —— 两种实际应用场景模拟
- oracle一个listener侦听多个实例的配置
热门文章
- 通过定义过滤器filter解决跨域问题
- Kafka查看topic、consumer group状态命令
- SCC的奇葩算法——Kosaraju
- mfc 嵌套类
- 修改 input[type=";radio";] 和 input[type=";checkbox";] 的默认样式
- Java 中的 try catch 影响性能吗?
- Asp.Net_序列化、反序列化
- SICP读书笔记 1.1
- 关于OBS获取显示器黑屏的解决办法
- Notes of Daily Scrum Meeting(12.18)