Consecutive Subsequence CodeForces - 977F
题目大意:输出一序列中的最大的连续数列的长度和与其对应的下标(连续是指 7 8 9这样的数列)
解题思路:
状态:把dp[i]定义为数列末尾为 i 的最大连续数列的长度值
状态转移方程:dp[i] = dp[i-1] + 1
再由最大连续数列最后一个值从后往前倒推出前面的所有值,到不是连续时停止
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = + ;
int dp[N];
int a[N];
int res[N];
int main() {
int n;
scanf("%d", &n);
int e, v;
int ans = ;
for(int i = ; i < n; i++) {
scanf("%d", &v);
a[i] = v;
dp[v] = dp[v-] + ;
if(ans < dp[v]) {
ans = dp[v];
e = i;
}
}
printf("%d\n", ans);
int tot = ;
int flag = a[e];
for(int i = e; i >= ; i--) {
if(a[i] == flag) {
res[tot++] = i + ;
flag--;
}
if(tot == ans) break;
}
for(int i = tot - ; i > ; i--) {
printf("%d ", res[i]);
}
printf("%d\n", res[]);
return ;
}