UVa 1471 防线
2024-08-29 23:22:21
https://vjudge.net/problem/UVA-1471
题意:给出一个序列,删除一个连续子序列,使得剩下的序列中有一个长度最大的连续递增子序列,输出个数。
思路:首先可以计算出以i结尾的最大连续递增子序列个数 f(i) 和以i开头的最大连续递增子序列 g(i)。之后就是动态规划吧,题目挺抽象,不太好解释,具体看代码吧。
#include<iostream>
#include<algorithm>
using namespace std; const int maxn = * + ; int n;
int a[maxn];
int f[maxn], g[maxn],d[maxn]; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int t;
cin >> t;
while (t--)
{
cin >> n;
for (int i = ; i <= n; i++)
cin >> a[i];
f[] = ;
for (int i = ; i <= n; i++)
f[i] = a[i] > a[i - ] ? f[i - ] + : ;
g[n] = ;
for (int i = n - ; i >= ; i--)
g[i] = a[i] < a[i + ] ? g[i + ] + : ;
int ans = ;
for (int i = ; i <= n; i++)
d[i] = << ;
for (int i = ; i <= n; i++)
{
//low_bound的返回值就是以a[i]为尾的连续递增子序列
int len = (lower_bound(d + , d + + i , a[i]) - (d + )) + g[i];
ans = max(len, ans);
d[f[i]] = min(a[i], d[f[i]]); //如果以i结尾的最大连续递增子序列个数相同,那么选择数小的
}
cout << ans << endl;
}
return ;
}
最新文章
- vim基本命令
- x01.FileProcessor: 文件处理
- 【Android】Handler、Looper源码分析
- DCMTK354之VC++ 2008 MFC应用程序配置完整过程
- (转)WordPress的主查询函数-query_posts()
- python测试开发django-3.url配置
- cannot find package ";context";
- ueditor的简单用法
- [Noip2015PJ] 求和
- Mybatis 在 insert 之后想获取自增的主键 id
- There are stopped jobs
- 【第四课】Linux的基础命令使用
- Python+Selenium+Unittest+Ddt+HTMLReport分布式数据驱动自动化测试框架结构
- 【题解】 bzoj2435: [Noi2011]道路修建 (傻逼题)
- 配置Oracle E-Business Suite Integrated SOA Gateway Release 12.1.2/12.1.3
- 一:php配置注意
- NetworkStateReceiver的简单应用
- linux安装教程以及使用时遇到的问题和解决方法
- 洛谷 P1410 子序列(DP)
- PCANet