摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : DP

實做 RMQ

參考 http://robertanders.pixnet.net/blog/post/27930664

但是仍不是最快的,所以還有待改進

建表O(Nlog2(N)) 查詢O(log2(N))

/*********************************************************/

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int f[500001][21]={0};
int MAX(int x,int y)
{
   if(x>y) return x;
   else return y;
}
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
main()
{
  int n2[21]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
  int a,b,N,M,st,en;
  while(scanf("%d",&N)==1)
      {        
         for(a=1;a<=N;a++)
            scanf("%d",&f[a][0]);
         int lg=(int)(log10(N)/log10(2.0))+1; 
         for(b=1;b<=lg;b++)
             for(a=1;a<=N;a++)
                  {
                     if(a+n2[b]/2>N) break;
                     f[a][b]=MAX(f[a][b-1],f[a+n2[b]/2][b-1]);
                  }    
         scanf("%d",&M);
         for(a=1;a<=M;a++)
             {
                scanf("%d %d",&st,&en);
                if(st>en)
                   {
                     int temp;
                     temp=st;
                     st=en;
                     en=temp;
                   }
                int l=en-st+1,ANS=0,t=0,flag=st;
                while(l!=0)
                    {
                       if(l%2==1)
                         {
                          ANS=MAX(f[flag][t],ANS);
                          flag+=n2[t];
                         }
                        l=l/2;
                        t++;
                    }
                printf("%d\n",ANS);
             }
      }
  return 0;
}

以下為所有的優化放入的"目前"最終產物

建表O(Nlog(N)) 查詢O(1)
/**********************************************************/

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int f[500001][20];
int MAX(int x,int y)
{
   if(x>=y) return x;
   else return y;
}
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
int lg2(int num)
{
   if(num<2) return 0;
   if(num<4) return 1;
   if(num<8) return 2;
   if(num<16) return 3;
   if(num<32) return 4;
   if(num<64) return 5;
   if(num<128) return 6;
   if(num<256) return 7;
   if(num<512) return 8;
   if(num<1024) return 9;
   if(num<2048) return 10;
   if(num<4096) return 11;
   if(num<8192) return 12;
   if(num<16384) return 13;
   if(num<32768) return 14;
   if(num<65536) return 15;
   if(num<131072) return 16;
   if(num<262144) return 17;
   if(num<524288) return 18;
}
main()
{
  int n2[21]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
  int a,b,N,M,st,en;
  while(scanf("%d",&N)==1)
      {        
         for(a=1;a<=N;a++)
            f[a][0]=input();
         int lg=lg2(N); 
         for(b=0;b<lg;b++,N-=n2[b])
             for(a=1;a<=N;a++)
                f[a][b+1]=MAX(f[a][b],f[a+n2[b]][b]);
         scanf("%d",&M);
         int temp,l,k;
         for(a=1;a<=M;a++)
             {
                st=input(),en=input();
                if(st>en)
                     temp=st,st=en,en,en=temp;
                l=en-st+1;
                k=lg2(l);
                printf("%d\n",MAX(f[st][k],f[en-n2[k]+1][k]));
             }
      }
  return 0;
}

以下是用線段樹所做出來的

在此題由於詢問沒有很大

在記憶體小的形況下 速度會++

感謝 liouzhou_101的提供

建表O(N) 詢問O(logN)

/**********************************************************/

#include<stdlib.h>
#include<stdio.h>
int A[500001],tree[1100001];
int MAX (int x,int y)
{
   if(x>=y) return x;
   else return y;
}
void set_tree(int l,int r,int k)
{
   if(l==r)  tree[k]=A[l];
   else
      {
         int m=(l+r)/2;
         set_tree(l,m,2*k);
         set_tree(m+1,r,2*k+1);
         tree[k]=MAX(tree[2*k],tree[2*k+1]);
      }
}
int  get(int l,int r,int k,int x,int y)
{
   if(l==x&&r==y)  return tree[k];
   else
      {
         int m=(l+r)/2;
         if(m>=y) return get(l,m,2*k,x,y);
         else if(m<x) return get(m+1,r,2*k+1,x,y);
         else return MAX(get(l,m,2*k,x,m),get(m+1,r,2*k+1,m+1,y));
      }
}
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
main()
{
  int N,a,x,y,M,t;
  while(scanf("%d",&N)==1)
      {
          for(a=1;a<=N;a++)
             A[a]=input();
          set_tree(1,N,1);
           scanf("%d",&M);
          for(a=1;a<=M;a++)
             {
              x=input(),y=input();
              if(x>y)  t=x,x=y,y=t;
              printf("%d\n",get(1,N,1,x,y));
             }
      }   
  return 0;
}