hdu-6406-dp+ST表 Taotao Picks Apples

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1446 Accepted Submission(s): 449

Problem Description

There is an apple tree in front of Taotao's house. When autumn comes,

). Can you answer all these queries?

Input

The first line of input is a single line of integer

, as described in the problem statement.

Output

For each query, display the answer in a single line.

Sample Input

1 5 3 1 2 3 4 4 1 5 5 5 2 3

Sample Output

1 5 3

　　如果能看出将这个序列分成两半之后利用一些预处理依旧能在log时间内得到答案的话就好办了，比赛的时候想了半天最后发现看错题目了，以为每次求一下LIS。。。这个是贪心的上升并非最优的。

　　我们提前做个ST表，用于处理区间最大值下标的查询。dp[0][i]表示从第一个元素到第i个元素的步数，dp[1][i]表示从i贪心的往后走的步数，对于每个<p,q> ，分成[1,p],[p,n] , 找到[1,p]之间的最大值下标j ，和[p,n]中大于这个最大值的下标k，答案就是 dp[0][j]+dp[1][k]。

 1 #include <iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int N,a[100100];
 5 int f[100100][20],dp[2][100100];
 6 void init(){
 7     for(int i=1;i<=N;++i)f[i][0]=i;
 8     for(int k=1;(1<<k)<=N;++k){
 9         for(int i=1;i+(1<<k)-1<=N;++i){
10             if(a[f[i][k-1]]>=a[f[i+(1<<(k-1))][k-1]]) f[i][k]=f[i][k-1];
11             else f[i][k]=f[i+(1<<(k-1))][k-1];
12         }
13     }    
14 }
15 int query(int L,int R){
16     if(R<L)return 0;
17     int k=0;
18     while((1<<(k+1))-1<=R-L) k++;
19     if(a[f[L][k]]>=a[f[R-(1<<k)+1][k]]) return f[L][k];
20     else return f[R-(1<<k)+1][k];
21 }
22 int main() {
23     int t,n,m,i,p,q;
24     cin>>t;
25     while(t--){
26         scanf("%d%d",&n,&m);
27         for(i=1;i<=n;++i)scanf("%d",a+i);
28         N=n,init();
29         dp[0][1]=1;
30         int maxn=1;
31         for(i=2;i<=n;++i){
32             if(a[i]>a[maxn]){
33                 dp[0][i]=dp[0][maxn]+1;
34                 maxn=i;
35             }
36             else dp[0][i]=-1;
37         }
38 
39         dp[1][n]=1;
40         for(i=n-1;i>=1;--i){
41             int l=i+1,r=n;
42             while(l<r){
43                 int mid=l+(r-l)/2;
44                 if(a[query(l,mid)]>a[i]) r=mid;
45                 else l=mid+1;
46             }
47             dp[1][i]=a[r]>a[i]?dp[1][l]+1:1;
48         }
49         while(m--){
50             scanf("%d%d",&p,&q);
51             int x=query(1,p-1),xx=a[x],ans=dp[0][x];
52             if(q>a[x]) xx=q,ans++;
53             int l=p+1,r=n;
54             while(l<r){
55                 int mid=l+(r-l)/2;
56                 if(a[query(p+1,mid)]>xx)r=mid;
57                 else l=mid+1;
58             }
59             if(a[l]>xx) ans+=dp[1][l];
60             cout<<ans<<endl;
61         }
62     }
63     return 0;
64 }

hdu-6406-dp+ST表 Taotao Picks Apples

相关推荐