首页 > 其他分享 >luogu P1410 子序列

luogu P1410 子序列

时间:2022-09-26 16:14:17浏览次数:58  
标签:min int luogu P1410 序列 长度 dp define

子序列

题目描述

给定一个长度为 \(N\)(\(N\) 为偶数)的序列,问能否将其划分为两个长度为 \(N / 2\) 的严格递增子序列。

输入格式

若干行,每行表示一组数据。

对于每组数据,首先输入一个整数 \(N\),表示序列的长度。之后 \(N\) 个整数表示这个序列。

输出格式

输出行数与输入行数相同。

对于每组数据,如果存在一种划分,则输出 Yes!,否则输出No!

样例 #1

样例输入 #1

6 3 1 4 5 8 7
6 3 2 1 6 5 4

样例输出 #1

Yes!
No!

提示

【数据范围】

共三组数据,每组数据行数<=50,0 <= 输入的所有数 <= 10^9

第一组(30%):N <= 20
第二组(30%):N <= 100

第三组(40%):N <= 2000

思路

我们显然知道这道题应该用dp来考虑
首先我们要维护的肯定有两个序列结尾是什么
我们还要维护当前两个序列的长度!
这样我们就可以设置:
dp[i][j]表示当前到第i位 并且有一个序列长度为j (另一个自然为i-j) 并且末尾为a[i] 另一个就可以直接存在dp[i][j]里
这样我们就可以考虑刷表枚举a[i+1]
if(a[i+1]>a[i])我们就可以继续放置在该长度为j的序列里
f[i+1][j+1]=min(f[i][j]);
if(a[i+1]>f[i][j])要是a[i+1]大于了另一序列最后那我们也可以放进那里面去
f[i+1][i-j+1]=min(a[i]);当然我们里面存的就是a[i](另一序列最后)
我们可以发现这样枚举是不重不漏地 并且 也具有合法性
最后贴上代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"Yes"
#define NO cout<<"No"
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[2010][2010];
void solve() {
    int n;
    while(cin>>n){
        vector<int>a(n+1);
        for(int i=1;i<=n;i++)cin>>a[i];
        memset(dp,0x3f3f,sizeof dp);
        dp[1][1]=0;//表示前i个数 选j个的且最后结尾是i剩下序列也是上升的min
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(dp[i][j]!=INF) {
                    if (a[i + 1] > a[i])dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
                    if (a[i + 1] > dp[i][j])dp[i + 1][i - j + 1] = min(dp[i + 1][i - j + 1], a[i]);
                }
            }
        }
        dp[n][n/2]==INF?NO:YES;cout<<'!'<<endl;
    }
}
signed main(){
    fast
    int T;T=1;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

标签:min,int,luogu,P1410,序列,长度,dp,define
From: https://www.cnblogs.com/ycllz/p/16731252.html

相关文章

  • 前后端开发模式,restful规范,序列化与反序列化,cbv源码
    1.前后端开发模式后端人员写前后端混合开发项目==》使用模板语法渲染   后端人员写前后端分离项目 ==》后端人员只负责写API,使用postman来测试接口,前端的人专......
  • 表单序列化得常用方法
    方法1:serialize():就是把表单信息序列化成一个字符串(认为最常用的方法)<html><head><scripttype="text/javascript"src="/jquery/jquery.js"></script><scriptty......
  • 单变量时间序列平滑方法介绍
    时间序列是由按时间排序的观察单位组成的数据。可能是天气数据、股市数据。,也就是说它是由按时间排序的观察值组成的数据。在本文中将介绍和解释时间序列的平滑方法,时间......
  • 【luogu P4218】珠宝商(SAM)(点分治)(根号分治)
    珠宝商题目链接:luoguP4218题目大意给你一棵树,每个点有一个字符。再给你一个字符串s。然后问你树上的所有简单的路径在s上的出现次数的和。思路一个比较神奇的题......
  • php反序列化的
    说明:​ 今天的CTF遇到php反序列化的问题,之前只是稍微了解,没有认真学习过,所以今天就懵了~,好吧,当不能上多次,今天就好好记录下突击的结果吧。1、介绍PHP的反序列化网络上......
  • 最长不下降子序列
    #include<bits/stdc++.h>usingnamespacestd;intdfs(int);intmax(int,int);intmaxn=0,n,a[10000],f[10000];intmain(){cin>>n;for(inti=1;i<=n;i......
  • 最长不下降子序列
    题目:设有由n(1≤n≤200))个不相同的整数组成的数列,记为:b(1)、b(2)、……、b(n)b(1)、b(2)、……、b(n)若存在i1<i2<i3<…<ie且有b(i1)<=b(i2)<=…<=b(ie)则称为长度为e......
  • 最长上升子序列(LIS)
    题目:LIS(LongestIncreasingSubsequence)为最长上升子序列:给定n个元素的数列,求最长的上升子序列长度(LIS)。一个数的序列ai,当a1<a2<…<aS的时候,我们称这个序列是......
  • PHP序列化基础知识
    魔术方法:注:魔术方法只有在类中被定义以后才可以触发PHP将所有以__(两个下划线)开头的类方法保留为魔术方法,这些都是PHP内置的方法。__construct()当一个对象创建时被......
  • 序列
    实验 项目名称:      序列的应用               一.   实验目的和要求 初步认识序列二.  实验环境 win10三.  实验过......