代码源每日一题div1 【哈希DP】连续子序列

た入场券 2024-03-31 11:44 37阅读 0赞

[连续子序列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![824f6dcd63de48109b574e3ec210a0d2.png][]

思路：

状态设计：dp\[i\]

含义：子序列结尾是a\[i\]的序列的最长子序列长度

状态转移：

直接去枚举上一个状态

上一个状态只能是一种:dp\[a\[i\]-1\]

因此不需要再一层for循环枚举从哪里转移过来

从dp\[a\[i\]-1\]转移过来

然后去输出方案，注意只需要输出一种方案即可

因此我们去找到第一个最大值对应的下标，然后输出方案即可

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e5+10;
    #define int long long
    map<int,int> dp;
    int n,mx=-1;
    int a[mxn];
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=1;i<=n;i++){
    		dp[a[i]]=max(dp[a[i]],dp[a[i]-1]+1);
    		mx=max(mx,dp[a[i]]);
    	}
    	for(auto it:dp){
    		if(it.second==mx){
    			cout<<it.second<<'\n';
    			int len=it.second;
    			for(int i=it.first-len+1;i<=it.first;i++) cout<<i<<" ";
    			cout<<'\n';
    			return 0; 		
    		}
    	}
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/10/problem/504
[824f6dcd63de48109b574e3ec210a0d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/ad53b2e6923049d3b2f26e835adfb427.png

发表评论取消回复

表情：

评论列表（有 0 条评论，37人围观）

还没有评论，来说两句吧...

相关阅读

相关代码源每日一题div1 DP 数组划分

[数组划分 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![3df804eb4f5b4

向右看齐/ 2024年03月31日 13:09/ 0 赞/ 17 阅读

相关代码源每日一题div1 枚举倍数优美！最长上升子序列

[优美！最长上升子序列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![6f04eef

悠悠/ 2024年03月31日 12:47/ 0 赞/ 20 阅读

相关代码源每日一题div1 【哈希DP】连续子序列

[连续子序列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![824f6dcd63de

た入场券/ 2024年03月31日 11:44/ 0 赞/ 38 阅读

相关【按位考虑DP】代码源每日一题div1 2023.02.02 与

[与 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 这太酷了，很符合我对DP的想象这DP太妙了

缺乏、安全感/ 2024年03月27日 11:42/ 0 赞/ 25 阅读

相关【代码源每日一题】最长有趣子序列

....为什么审核一直不过题意： ![4de6189cd74886d6881b1a6cb06d0d89.png][] 思路：感觉这道题我绝对写过啊，但是不知道为什么

我就是我/ 2024年03月26日 20:00/ 0 赞/ 39 阅读

相关【代码源每日一题div1】树状数组数数

就是把权值树状数组反过来，感觉很妙啊 [数数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意

蔚落/ 2024年03月26日 19:46/ 0 赞/ 20 阅读

相关【贪心】代码源每日一题div2 背包

[背包 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![c70769545d9f444

浅浅的花香味﹌/ 2024年03月16日 18:13/ 0 赞/ 28 阅读

相关【简单DP】代码源每日一题div2 树

[树 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![a4d4c61e3adb48be

Dear 丶/ 2024年03月16日 16:49/ 0 赞/ 18 阅读

相关【树形DP+直径思想】代码源每日一题div1 三进制循环

[三进制循环 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![81c27010b10b

浅浅的花香味﹌/ 2024年03月16日 16:44/ 0 赞/ 11 阅读

相关【状态设计优化DP】代码源每日一题div1 等差数列

[等差数列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![64f437cfde1a4

我就是我/ 2024年03月16日 14:48/ 0 赞/ 11 阅读