Codeforces Round #479 (Div. 3) F. Consecutive Subsequence

标签： DP

题目链接

分析

虽然是不难的dp，但是放在F题的位置以为很难，我还是想复杂了结果搞了好久才搞出来，而且还遇到了std::unordered_map的坑。CF上有组数据专门卡unordered_map然后就tle了。 因为unordered_map是hash存储，所以会将hash值相同的放在一个桶里，但是在桶中查找的时候复杂度是$O(n)$的，在codeforces上找到了如下的优化方法

1unordered_map<int,int>mp;
2mp.reserve(1024);
3mp.max_load_factor(0.25);

这样就不会tle了。 具体原理看下面两个链接吧： http://codeforces.com/blog/entry/21853 http://en.cppreference.com/w/cpp/container/unordered_map/reserve

代码

1#include <iostream>
2#include <cstring>
3#include <algorithm>
4#include <vector>
5#include <cstdio>
6#include <map>
7#include <unordered_map>
8using namespace std;
9const int maxn=200050;
10int a[maxn];
11unordered_map<int,int> dp;
12int main(){
13	dp.reserve(maxn);
14	dp.max_load_factor(0.25);
15
16	int n;
17	scanf("%d", &n);
18	int M=0,e=0;
19	for(int i = 0; i < n; ++i){
20		scanf("%d", a+i);
21		int& u=dp[a[i]];
22		if(dp.count(a[i]-1)) u=max(u,dp[a[i]-1]+1);
23		else u=1;
24		if(u>M){
25			M=u;
26			e=a[i];
27		}
28	}
29	int b=e-M+1;
30	cout << M << endl;
31	for(int i = 0; i < n; ++i){
32		if(a[i]==b){
33			printf("%d ", i+1);
34			b++;
35		}
36	}
37	return 0;
38}