子序列
题目描述
给定一个长度为 \(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