[HDU] 4513 吉哥系列故事—

[HDU] 4513 吉哥系列故事——完美队形II

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4513

方法：模拟，定义数组counts[i]记录当第i个元素必须以一个序列最后一个元素的身份选择出来，该序列的长度是多大，使用countsEqual[i]表示第i元素直接前面包括自己有多少个连续的数字的值等于它自己。

如对于数据：

　　index: 1 2 3 4 5 6 7 8 9 10 11 12　　

　　value:　　 1 11 12 21 25 25 25 25 21 12 12 12

counts[i]：　　1 1 1 1 1 2 3 4 6 8 2 3

countsEqual[i]:1 1 1 1 1 2 3 4 1 1 2 3

在严格上升的区间里（第一个数默认为一个严格的上升区间，程序中是通过在数组的第一个数前面在加一个负数来实现），每一个 counts[i]和countsEqual[i]都等于1，自成一个序列.

在严格的下降区间里，每一个counts[i]都为1，而countsEqual[i]要分情况讨论，首先获取其前一个数字,下标为i-1(这里的i一定大于等于2，因为第一个数假定是在一个严格的上升区间内)，获取的 counts[i-1],若i-1-counts[i-1]个元素存在且等于第i元素，则counts[i] = counts[i-1]+2，标识合法序列得到扩展；如上述数据，当扫描到第10个数12时，

nums[10-1-counts[10-1]] == nums[10] == 12,则nums[10] =nums[10-1]+2=8;

否则，counts[i]和countsEqual[i]都等于1，自成一个序列。

在严格的相等区间里，分情况讨论，若在进入该区间前是一个严格上升区间，则说明该区间其实是在非降区间中，每一个 counts[i]和countsEqual[i]都等于第i个数在该区间中已经连续的个数，如上述第6个元素，其在严格的相等区间出现时，已经连续了2个。

若在进入该区间前是一个严格下降区间，则说明该区间其实是在非升区间中，counts[i]同上处理，而countsEqual[i]要分情况讨论，同样首先获取其前一个数字,下标为i-1(这里的i一定大于等于2，因为第一个数假定是在一个严格的上升区间内)，获取的 counts[i-1],若i-1-counts[i-1]个元素存在且等于第i元素，则counts[i] = counts[i-1]+2，合法序列得到扩展；否则counts[i]就等于countsEqual[i]，如上述到第11个数。

代码：

#include <iostream>
#include <queue>
#include <map>
#include<algorithm> 
using namespace std;
int nums[100001];
int n;
int countsEqual[100001];
int counts[100001];
int main()
{
    int tc = 0;
    scanf("%d",&tc);
    while(tc>0)  
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&nums[i]); 
        int max=0;
        int j = 1;
		int last=nums[0]=-1;
		bool increase=true;
		memset(countsEqual,0,sizeof(countsEqual));
		memset(counts,0,sizeof(counts));
        while(j <=n)
        {
			if(nums[j]>last)
			{
				while(nums[j]>last && j<=n)
				{
					 increase=true;
					 countsEqual[j]=1;
					 counts[j]=1;
					 max = max > 1 ? max :1;
					 last = nums[j];
					 j++;
				}
			}
			else if(nums[j]==last)
			{
				while(nums[j]==last && j<=n )
				{
					countsEqual[j]= j>=2 ? (countsEqual[j-1]+1):1;
					if(increase)
					{	
						 counts[j] = countsEqual[j];
						 max = max > counts[j] ? max :counts[j];
					}
					else
					{
						int t =counts[j-1];
						if(j-1-t >0 && nums[j-1-t]==nums[j])
						{
							max = max >(t+2) ? max : (t+2);
							counts[j]=t+2;
						}
						else
						{
							max = max > countsEqual[j] ? max :countsEqual[j];
							counts[j] = countsEqual[j];
						}
					}
					last = nums[j];
					j++;
				}
			}
			else if(nums[j]<last)
			{
				while(nums[j]<last && j<=n )
				{
					increase=false;
					countsEqual[j] = 1;
					int t =counts[j-1];
					if(j-1-t >0 && nums[j-1-t]==nums[j])
					{
						max = max >(t+2) ? max : (t+2);
						counts[j] = t+2;
					}
					else
					{
						 max = max > 1 ? max :1;
						 counts[j]=1;
					}
					last = nums[j];
					j++;
				}
			}
        }
		for(int i=1;i<=n;i++)
			max = max > counts[i] ? max :counts[i];
        cout<<max<<endl;
        tc--;
    }
    return 0;
}

感想：好好模拟，要思路清晰