HPU 1007: 严格递增连续子段（贪心）

1007: 严格递增连续子段 [模拟]

时间限制: 1 Sec 内存限制: 128 MB

提交: 244 解决: 18 统计

题目描述

给定一个有NN个正整数组成的序列，你最多可以改变其中一个元素，可以修改为任意的整数。问可以得到的严格递增连续子段的最大长度。

输入

第一行输入一个整数TT，代表有TT组测试数据。

每组数据占两行，第一行输入一个整数NN，代表元素个数。

下面一行有NN个正整数ai(ai<231)ai(ai<231)。

注：1<=T<=100,1<=N<=1000001<=T<=100,1<=N<=100000。

输出

对每组测试数据输出一个整数代表可以得到的严格递增连续子段的最大长度。

样例输入

2

4

1 2 3 4

4

1 2 2 4

样例输出

4

4

提示

第一组数据已经是严格递增连续子段了，不需要修改。

第二组数据可以将第三个元素修改为3，这样可以得到长度为4的严格递增连续子段。

一开始的思路是dp，但是看了学长们的题解后竟然是贪心，看了好久代码才理解

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

int a[maxn];

struct wzy{

	int start,starti,end,endi,len;

}p[maxn];

int main()

{

	int t,n,i;

	cin>>t;

	while(t--)

	{

		int k=0,res=1;

		int max_len=0;

		memset(a,0,sizeof(a));

		cin>>n;

		cin>>a[1];

		p[k].start=a[1];

		p[k].starti=1;

		for(i=2;i<=n;i++)

		{

			cin>>a[i];

			if(a[i]<=a[i-1])

			{

				p[k].end=a[i-1];

				p[k].endi=i-1;

				p[k].len=res;

				k++;

				p[k].start=a[i];

				p[k].starti=i;

				max_len=max(max_len,res);

				res=1;

			}

			else res++;

		}

		p[k].len=res;

		p[k].end=a[n];

		p[k].endi=n;

		k++;

		max_len=max(max_len,res);

		if(k>1) max_len++;

		for(i=0;i<k-1;i++)

		if(p[i].end+1<a[p[i+1].starti+1]||p[i].end-1>=1&&a[p[i].endi-1]+1<p[i+1].start)

			max_len=max(max_len,p[i].len+p[i+1].len);

		cout<<max_len<<endl;

	}

	return 0;

}