問題 E: 最長上升字串

時間限制: 3 Sec  記憶體限制: 128 MB

題目描述

給定n個整數，對其進行m次查詢。每次查詢是一個範圍l到r，求出l到r的最長上升連續子串。上升連續子串的定義為一個連續的子串且嚴格遞增。

輸入

第一行是一個整數T，代表測試資料的組數。每組資料中第一行是一個整數n,m，代表有一共有n個人，m個查詢。第二行共有n個整數，接下來m行是m次查詢，每行兩個整數l,r。

輸出

共T行，每行m個整數，代表最長上升連續字串。其中T<=50,m<1e5,每個數的大小不超過1e9。

樣例輸入

1
4 2
3 2 4 5
1 3
1 4
           

樣例輸出

2 3
           

解法一： 直接搜尋，但這題還是用動态規劃做比較好接受，解法二在下面

#include<cstdio>
#include<algorithm>
using namespace std;

int arr[10000];
int t,n,m,l,r,ans;

void solve(int now,int index,int lenth)
{
    if(now==r)
    {
        ans=max(ans,lenth+1);
        return;
    }
    if(arr[index]>arr[now]) 
		solve(index,index+1,lenth+1);
    else solve(now,index+1,lenth);
}

int main(){
    
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%d%d",&n,&m);
        for(int j=1;j<=n;j++) scanf("%d",&arr[j]);
        for(int k=0;k<m;k++) 
        {
            scanf("%d%d",&l,&r);
            ans=0;
            for(int p=l;p<r;p++)
            {
            	solve(p,p+1,0);
	    }
            printf("%d ",ans);
        }
    }
	return 0;
}
           

解法二： 動态規劃

#include<cstdio>
#include<algorithm>
using namespace std;

int arr[10000],dp[10000];
int t,n,m,l,r,ans;

int main(){
    
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%d%d",&n,&m);
        for(int j=1;j<=n;j++) scanf("%d",&arr[j]);
        for(int k=0;k<m;k++) 
        {
            scanf("%d%d",&l,&r);
            ans=0;
            for(int p=l;p<=r;p++)
			{
				dp[p]=1;
				for(int q=l;q<p;q++)
				{
					if(arr[q]<arr[p]&&p-q==1) dp[p]=max(dp[p],dp[q]+1);
				}
				ans=max(ans,dp[p]);
			} 
            printf("%d ",ans);
        }
    }
	return 0;
}