sdnu 1040 LIS-白红宇

sdnu 1040 LIS

阅读量：332 次

发布时间：2019-03-03

本文共 782 字，大约阅读时间需要 2 分钟。

输入改了好多次这个最舒服

就分别求最长上升子序列和最大下降子序列

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include
       
        using namespace std;typedef long long ll;const int Max = (int)1e6 + 9;const ll mod = 1000000007;int a[Max], dp1[Max], dp2[Max];char x[Max];int max1 = -1, max2 = -1;int i = 0;char c;int main(){   	while(~scanf("%d", &a[++i]))    {           getchar();        dp1[i] = dp2[i] = 1;//  每个初始都是1        for(int j = 1; j < i; j++)        {               if(a[i] > a[j])                dp1[i] = max(dp1[i], dp1[j] + 1);            else dp2[i] = max(dp2[i], dp2[j] + 1);        }        max1 = max(max1, dp1[i]);        max2 = max(max2, dp2[i]);    }    //for(int j = 1; j <= i; j++) cout << dp1[j] << " ";    printf("%d,%d\n", max2, max1 - 1);	return 0;}