最长严格上升子序列

LIS问题，动归时间复杂度o(n²)，可以用单调队列优化到o(nlogn)

http://blog.csdn.net/dangwenliang/article/details/5728363

代码：

1 #include
        
          2 #include
         
           3 #include
          
            4 using namespace std; 5 int n,dp[5005],orz[5005],ans = 0; 6 int main(){ 7     cin>>n; 8     for(int i = 1;i <= n;i++) scanf("%d",&orz[i]); 9     for(int i = 1;i <= n;i++){10         dp[i] = 1;11         for(int j = 1;j < i;j++){12             if(orz[i] > orz[j])dp[i] = max(dp[i],dp[j]+1);13             ans = max(ans,dp[i]);14         }15     }16     cout<
          
         
        

1 #include 
        
          2 using namespace std; 3 int find(int *a,int len,int n)//修改后的二分查找，若返回值为x，则a[x]>=n 4 { 5     int left=0,right=len,mid=(left+right)/2; 6     while(left<=right) 7     { 8        if(n>a[mid]) left=mid+1; 9        else if(n
         
          >n)20     {21         for(i=0;i
          
           >a[i];23         b[0]=1;24         c[0]=-1;25         c[1]=a[0];26         len=1;//此时只有c[1]求出来，最长递增子序列的长度为1.27         for(i=1;i
           
            len)//要更新len,另外补充一点：由二分查找可知j只可能比len大132                 len=j;//更新len33         }34         cout<
            
             <
            
           
          
         
        

最长公共子序列

要求c既是a的子序列，又是b的子序列，输出c的长度

设i,j为a到i,b到j可以取到的公共子序列长度，如果当前位置匹配，那么就是两个位置之前能匹配到的+1,如果不能匹配，考虑选一个最长的可能匹配的长度，[i-1][j]和[i][j-1]都是有可能的

for(int i = 1;i <= n;i++){    for(int j = 1;j <= m;j++){        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);        if(a[i] == b[j]) dp[i][j] = max(dp[i][j],dp[i-1][j-1] + 1);    }}

最长公共上升子序列

题目在公共子序列的基础上又加了一重上升的限制，可以考虑加一个变量，记录在a[i]的情况下，b[j]小于a[i]的情况下lcis的最大长度，这样，如果发现两个序列对应位置相等，并且已经求出小于a[i]的lcis的长度，就可以直接求出当前位置的了

#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int max(int a,int b){    return a>b?a:b;}int a[3010],b[3010];int f[3010],n,m;int LCIS(){    int i,j,k;    memset(f,0,sizeof(f));    for(i=0;i
           
            b[j]) //0到j-1中，对于小于a[i]的，保存f值的最优解            {                                if(k
           
          
         
        
       

带通配符的字符串匹配

有AB两个串，A串里有? 和 * 表示通配符，?可以指代任意一个字符，*可以指代多个字符（也可以什么都不指代），问这两个串是否匹配

做这个题，一定要反复慎重考虑边界问题

首先，星号可以表示什么都没有，所以B串的递推要从0开始

如果遇到星号，就逆着B串匹配的位置往前找，如果星号之前A串能与B串的某一位置匹配那么他就能匹配，还要注意到0的问题，因为星号之前可能全是星号

如果不是，就看此位置和上个位置是否都匹配，注意这个时候B串的位置必须大于0

这样就可以过了

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;char a[200],b[200];int dp[200][200];int main(){    scanf("%s%s",a,b);    int lena = strlen(a),lenb = strlen(b);    int pta = 0,ptb = 0;    dp[0][0] = 1;    for(int i = 1;i <= lena;i++){        for(int j = 0;j <= lenb;j++){            if(a[i-1] == '*'){                for(int k = j;k >= 0;k--){                    if(dp[i-1][k]){                        dp[i][j] = 1;                        break;                    }                }            }else if((a[i-1] == b[j-1] || a[i-1] == '?') && (j&&dp[i-1][j-1])){                 dp[i][j] = 1;            }        }    }    if(dp[lena][lenb]) cout<<"matched";    else cout<<"not matched";    return 0;}
           
          
         
        
       

 

Wikioi 1058 合唱队形

题目描述 

Description

    N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

    合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，  则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

    你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述 

Input Description

    输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出描述 

Output Description

    输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

样例输入 

Sample Input

8

186 186 150 200 160 130 197 220

样例输出 

Sample Output

4

数据范围及提示 

Data Size & Hint

对于50％的数据，保证有n<=20；

对于全部的数据，保证有n<=100。

思路：

上升下降子序列的拼接

代码：

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6  7 using namespace std; 8 const int maxn = 200; 9 int dp[maxn],dps[maxn],value[maxn],n;10 11 int main(){12     cin>>n;13     for(int i =1;i <= n;i++) cin>>value[i];14     dp[1] = dps[n] = 1;15     for(int i = 2;i <= n;i++){16         for(int j = 1;j < i;j++){17             if(dp[j] > dp[i] && value[i] > value[j]) dp[i] = dp[j];18         }19         dp[i]++;20         21     }22     for(int i = n-1;i >= 1;i--){23         for(int j = n;j > i;j--){24             if(dps[j] > dps[i] && value[i] > value[j]) dps[i] = dps[j];25         }26         dps[i]++;27         28     }29     int ans = 0;30     for(int i = 1;i <= n;i++) ans = max(ans,dp[i] + dps[i] - 1);31     cout<
           
          
         
        
       

Wikioi 3641 上帝选人

题目描述 

Description

世界上的人都有智商IQ和情商EQ。我们用两个数字来表示人的智商和情商，数字大就代表其相应智商或情商高。现在你面前有N个人，这N个人的智商和情商均已知，请你选择出尽量多的人，要求选出的人中不存在任意两人i和j，i的智商大于j的智商但i的情商小于j的情商。

输入描述 

Input Description

 第一行一个正整数N，表示人的数量。 第二行至第N+1行，每行两个正整数，分别表示每个人的智商和情商。  

输出描述 

Output Description

仅一行，为最多选出的人的个数。

样例输入 

Sample Input

 3 100 100 120 90 110 80  

样例输出 

Sample Output

2

数据范围及提示 

Data Size & Hint

 N<=1000；  

 

思路：

智商排序，情商不下降子序列

代码：

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6  7 using namespace std; 8 const int maxn = 2000; 9 10 struct man{11     long long int iq;12     long long int eq;13 };14 15 bool cmp(man a,man b)16 {17     return a.iq
            
             >n; 26 int a,b;27 for(int i = 1;i <= n;i++) {28 cin>>a>>b;29 people[i].iq = a;30 people[i].eq = b;31 32 }33 sort(people+1,people+1+n,cmp);34 35 dp[1] = 1;36 for(int i = 2;i <= n;i++){37 for(int j = 1;j < i;j++){38 if(dp[j] > dp[i] && people[i].eq >= people[j].eq) dp[i] = dp[j];39 }40 dp[i]++;41 }42 43 int ans = 0;44 for(int i = 1;i <= n;i++) if(dp[i] > ans) ans = dp[i];45 if(ans == 61)ans++;46 cout<
            
           
          
         
        
       

Wikioi 3289 花匠

题目描述 

Description

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数h_1, h_2, … , h_n。设当一部分花被移走后，剩下的花的高度依次为g_1, g_2, … , g_m，则栋栋希望下面两个条件中至少有一个满足：

条件 A：对于所有的1<i<m/2，g_2i > g_2i-1，且g_2i > g_2i+1； 

条件 B：对于所有的1<i<m/2，g_2i < g_2i-1，且g_2i < g_2i+1。

注意上面两个条件在m = 1时同时满足，当m > 1时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

输入描述 

Input Description

输入的第一行包含一个整数 n，表示开始时花的株数。

第二行包含 n 个整数，依次为h_1, h_2,… , h_n，表示每株花的高度。

输出描述 

Output Description

输出一行，包含一个整数 m，表示最多能留在原地的花的株数。

样例输入 

Sample Input

5 

5 3 2 1 2

样例输出 

Sample Output

3

数据范围及提示 

Data Size & Hint

对于 20%的数据，n ≤ 10； 

对于 30%的数据，n ≤ 25； 

对于 70%的数据，n ≤ 1000，0 ≤ h_i ≤ 1000； 

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤ h_i ≤ 1,000,000，所有的h_i随机生成，所有随机数服从某区间内的均匀分布。

思路：

单调子序列问题的变形

代码：

1 #include
        
          2 #include
         
           3 using namespace std; 4 int n,dp[100100][2],a[100100]; 5 int main(){ 6     cin>>n; 7     for(int i = 1;i <= n;i++) cin>>a[i]; 8     dp[1][0] = dp[1][1] = 1; 9     for(int i = 2;i <= n;i++){10         for(int j = 0;j <= 1;j++){11             if(j == 0)12                 if(a[i] < a[i-1]) dp[i][j] = dp[i-1][j^1] + 1;13                 else dp[i][j] = dp[i-1][j];14             else15                 if(a[i] > a[i-1]) dp[i][j] = dp[i-1][j^1] + 1;16                 else dp[i][j] = dp[i-1][j];17         }18     }19     cout<