Hlg 1709 巧妙思维题.cpp

题意：

　　给出n个数，求出改变某个数后能得到最长的严格上升子序列

思路：

　　用一个数组pre[i]和suf[i]分别表示第i个数前的严格上升子序列有多长，第i个数后的严格上升子序列有多长

　　如果arr[i]的前一个数比后一个数起码小1的话..找出max(pre[i]+suf[i]+1)，否则max(ans, max(suf[i]+1, pre[i]+1))

Tips：

　　注意可能出现1 1 2 3 4 这样的情况，这时候就只能是4了..

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n;
 9     int arr[10010], pre[10010], suf[10010];
10     int ans;
11     while(~scanf("%d", &n)) {
12         ans = -1;
13         memset(pre, 0, sizeof(pre));
14         memset(suf, 0, sizeof(suf));
15         for(int i = 0; i < n; ++i) {
16             scanf("%d", &arr[i]);
17             int j = i-2;
18             while(j >= 0 && arr[j] < arr[j+1]) j--;
19             pre[i] = i-j-1;
20             if(i == 0) pre[i] = 0;
21         }
22         for(int i = 0; i < n; ++i) {
23             int j = i+2;
24             while(j < n && arr[j-1] < arr[j]) j++;
25             suf[i] = j-i-1;
26             if(i == n-1) suf[i] = 0;
27         }
28     /*********************debug******************
29     for(int i = 0; i < n; ++i)
30         printf("____%d %d\n", pre[i], suf[i]);
31     *********************debug******************/
32         for(int i = 0; i < n; ++i)
33             if(arr[i-1] < arr[i+1]-1)
34                 ans = max(ans, pre[i]+suf[i]+1);
35             else if(i != 1 || (i == 1 && arr[i] != 0)) ans = max(ans, max(suf[i]+1, pre[i]+1));
36        // if(arr[1] != 1) ans = max(ans, suf[0]+1);
37         printf("%d\n", ans);
38     }
39     return 0;
40 }

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1709