hdu6357 Hills And Valleys (最长不下降子序列)
2024-10-07 07:59:49
题意:
给你0~9的字符串,问你翻转哪个区间后使得其最长不下降子序列长度最长
思路:
因为字符是0~9,所以我们可以定义一个b数组来枚举L,R,
去和原来的字符串去求最长公共子序列长度,不断更新求最大值
然后在其中记录路径,不断回缩去求此时的L,R
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100005
int n,b[];
char str[N];
int a[N],dp[N][],pre[N][]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int ans=,ansl,ansr; scanf("%d %s",&n,str);
for(int i=;i<n;i++) a[i+]=str[i]-'';
for(int L=;L<=;L++)
for(int R=L;R<=;R++){
int tot=;
for(int k=;k<=L;k++) b[++tot]=k;
for(int k=R;k>=L;k--) b[++tot]=k;
for(int k=R;k<=;k++) b[++tot]=k;
//更新LCS
for(int i=;i<=n;i++)
{
int t=;
for(int j=;j<=tot;j++)
{
if(dp[i-][j]>dp[i-][t]) t=j;
pre[i][j]=t;
dp[i][j]=dp[i-][t]+(a[i]==b[j]);
}
}
for(int j=tot;j>=;j--)
if(dp[n][j]>ans){
ans=dp[n][j];
int t=j,l=,r=;
for(int i=n;i>=;i--){
if(!l&&t<=L+) l=i+;
if(!r&&t<=R+) r=i;
t=pre[i][t];
}
if(r==) r=l;
ansl=l;ansr=r;
}
}
printf("%d %d %d\n",ans,ansl,ansr);
}
return ;
}
参考博客:https://www.cnblogs.com/zquzjx/p/10333418.html
最新文章
- SQL Server 备份迁移策略
- ASP.NET MVC 从零开始 - create and run
- linux搭建mysql 5.6.28
- angular2 的依赖注入
- 再看.net本质(二)
- Kafka消息模型
- OpenJudge / Poj 1928 The Peanuts C++
- iOS 开发之 ReactiveCocoa(基础)
- 关于http状态码204理解
- java学习之线程池的实现
- sql事务,在sql2000里判断执行是否成功用@@ERROR 判断
- ngx-push-stream模块源码学习(五)——内存清理
- .NEL IL实现对象深拷贝
- HTTP协议扫盲(八 )响应报文之 Transfer-Encoding=chunked方式
- 【Visual C++】游戏编程学习笔记之七:键盘输入消息
- [转]java中作用域public private protected 以及不写的区别
- linux shell 之尝试编写 企业级 启动脚本
- Ubuntu16.04安装配置和使用ctags
- docker 应用-1(安装以及基础命令)
- python下彻底解决浏览器多标签打开与切换问题