codeforce #505D - Recovering BST 区间DP
2024-09-29 02:59:54
题意:
有一个递增序列,问能不能构建出一颗每条边的端点值都不互质的二叉排序树。
思路:
区间DP,但是和常见的区间DP不一样,
这里dp【i】【j】表示的是区间【i,j】能否以i为根建立一个小二叉排序树。
所以可以得到dp【i】【j】 为true, 要求在【i+1,j】中有一个k,dp【k】【i+1】和dp【k】【j】都为true。
或者在i点的左边取件中,即要求在【j】【i-1】中有一个k,dp【k】【j】和dp【k】【i-1】都为true。
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
//#pragma GCC optimize(3)
//#pragma comment(linker, "/STACK:102400000,102400000") //c++
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull; typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行
#define REP(i , j , k) for(int i = j ; i < k ; ++i)
//priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFFLL; //
const ll nmos = 0x80000000LL; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3fLL; //
const int mod = ; const double PI=acos(-1.0); // #define _DEBUG; //*//
#ifdef _DEBUG
freopen("input", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
/*-----------------------showtime----------------------*/
const int maxn = ;
ll a[maxn],mp[maxn][maxn],dp[maxn][maxn];
ll gcd(ll a,ll b){
if(b==)return a;
return gcd(b,a%b);
} int main(){
int n;
scanf("%d", &n);
for(int i=; i<=n; i++){
scanf("%I64d", &a[i]);
} for(int i=; i<=n; i++){
for(int j=; j<=n; j++)
{
if(i==j)dp[i][j] = ;
mp[i][j] = (gcd(a[i],a[j]) == ?:);
}
} for(int len = ; len <= n; len++){
for(int i=; i<=n; i++){
int le = i - len;
if(le >= ){
for(int k = le ; k < i; k++){
if(dp[k][le] && dp[k][i-] && mp[k][i]){
dp[i][le] = ;
break;
}
}
} int ri = i + len;
if(ri <= n){
for(int k = i+; k <= ri ; k++){
if(dp[k][i+] && dp[k][ri] && mp[i][k]){
dp[i][ri] = ;
break;
}
}
}
}
} for(int i=; i<=n; i++){
if(dp[i][] && dp[i][n]){
puts("Yes");
return ;
}
}
puts("No");
return ;
}
CF1025D
最新文章
- sql中查询中的when...then 语句
- 从DataGridView导出Excel
- 【java】jackson 中JsonFormat date类型字段的使用
- border-width和border其它属性配合实现的小三角形标签效果
- Equinox P2的学习
- Oracle中的null
- iOS-Runtime-Headers
- Android优化
- C++之路进阶——codevs1362(网络扩容)
- ThreadLocal,Java中特殊的线程绑定机制
- windows2003 单网卡 搭建vpn ,windows 2008 R2 类似吧。网上转的,自己加了点经验总结
- 第六篇、微信小程序-form组件
- iOS: 学习笔记, Swift名字空间
- Linux中date命令的各种实用方法--转载
- js 判断url的?后参数是否包含某个字符串
- web api简单验证实现办法
- 根据list<;Object>;中的某个字段排序
- HDU 4777 Rabbit Kingdom
- Java异常类(Throwable)
- UltraEdit中使用正则表达式替换