hdu4512（最大公共上升子序列）

這道題我之前做過一次，當時沒想明白，wa了。今天再次看見，重新審視題目後，確定這就是一個最大上升子序列，當時還挺興奮的，可後面發現我不知道該怎麼去區分存不存在中間最高點的情況。思考了許久，還是沒想明白，然後還是去查解題報告了。。。。。

這個算法非常巧妙，用暴力去枚舉所有有中間點和沒有中間點的情況，然後取其中最大的。這算是什麼？半DP半暴力？暴力與美學的結合？

關於最大公共上升子序列的算法，我之前有一篇博客已經解釋過了，也就不再解釋了。

鏈接：hdu 1423（最大公共上升子序列）

[cpp]  #include<stdio.h>  
#include<string.h>  
#define N 205  
int a[N],b[N],ans[N]; 
int Max(int x,int y) 
{ 
    return x>y?x:y; 
} 
int LCIS(int x,int y) 
{ 
    memset(ans,0,sizeof(ans)); 
    int sum; 
    int i,j,k; 
    for(i=1;i<=x;i++) 
    { 
        k=0; 
        for(j=1;j<=y;j++) 
        { 
            if(b[j]<a[i]&&ans[k]<ans[j]) 
                k=j; 
            if(b[j]==a[i]) 
                ans[j]=ans[k]+1; 
        } 
    } 
    sum=0; 
    for(i=1;i<=y;i++) 
        sum=Max(sum,ans[i]); 
    return sum*2; 
} 
int main() 
{ 
    int T; 
    scanf("%d",&T); 
    while(T--) 
    { 
        int n; 
        int i; 
        scanf("%d",&n); 
        for(i=1;i<=n;i++) 
        { 
            scanf("%d",&a[i]); 
            b[n-i+1]=a[i]; 
        } 
        int ans; 
        ans=0; 
        for(i=1;i<=n;i++) 
        { 
            ans=Max(LCIS(i,n-i),ans); 
            ans=Max(LCIS(i,n-i+1)-1,ans); 
        } 
        printf("%d\n",ans); 
    } 
    return 0; 
} 

#include<stdio.h>
#include<string.h>
#define N 205
int a[N],b[N],ans[N];
int Max(int x,int y)
{
 return x>y?x:y;
}
int LCIS(int x,int y)
{
 memset(ans,0,sizeof(ans));
 int sum;
 int i,j,k;
 for(i=1;i<=x;i++)
 {
  k=0;
  for(j=1;j<=y;j++)
  {
   if(b[j]<a[i]&&ans[k]<ans[j])
    k=j;
   if(b[j]==a[i])
    ans[j]=ans[k]+1;
  }
 }
 sum=0;
 for(i=1;i<=y;i++)
  sum=Max(sum,ans[i]);
 return sum*2;
}
int main()
{
 int T;
 scanf("%d",&T);
 while(T--)
 {
  int n;
  int i;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
  {
   scanf("%d",&a[i]);
   b[n-i+1]=a[i];
  }
  int ans;
  ans=0;
  for(i=1;i<=n;i++)
  {
   ans=Max(LCIS(i,n-i),ans);
   ans=Max(LCIS(i,n-i+1)-1,ans);
  }
  printf("%d\n",ans);
 }
 return 0;
}