题目链接

http://codeforces.com/problemset/problem/447/C

题目大意

给你n个数， 可以改变一个数值， 问你最长严格递增序列的长度

思路

这题的意思很明确， 但是如何实现以及细节处理上存在很大问题 首先实现上， 如果只用一个数组去模拟这个过程求最大值，很容易写挫且会有bug 我们先不考虑修改一个数， 从前往后用up[i]记录第i个位置上升序列的长度，从后往前用dw[i]记录第i个位置下降序列的长度 这样考虑修改一个数之后 ans = max(ans, up[i] + dw[i] + 1) 细节方面， 只有num[i] + 1 < num[i+2] 才能修改num[i+1] 还有就是ans 还可以 = max(ans, max(up[i] + 1, dw[i] + 1)), 也就是在最长序列头或者尾修改一个数， 这时要小心一个bug， 就是n个数都递增时， ans可能>n, 这显然是错的， 要特判一下

代码

#include<bits/stdc++.h> using namespace std; const int M = 1e6 + 5; int num[M], up[M], dw[M]; int main() { int n; memset(up, 0, sizeof(up)); memset(dw, 0, sizeof(dw)); scanf("%d", &n); for(int i=0; i<n; ++i) scanf("%d", num+i); int tot = 1; up[0] = 1, dw[n-1] = 1; for(int i=1; i<n; ++i) { if(num[i] > num[i-1]) ++tot; else tot = 1; up[i] = tot; } tot = 1; for(int i=n-2; i>=0; --i) { if(num[i] < num[i+1]) ++tot; else tot = 1; dw[i] = tot; } int ans = 1; for(int i=0; i<n-2; ++i) { if(num[i] + 1 < num[i+2]) ans = max(ans, up[i] + dw[i+2] + 1); } for(int i=0; i<n; ++i) ans = max(ans, max(up[i]+1, dw[i]+1)); if(ans > n) ans = n; printf("%d\n", ans); return 0; }

反思

代码实现能力太差了， 集训半个月前一路wa过去， 现在还是一路wa过去。。。orz