sequence2

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 220 Accepted Submission(s): 90

Problem Description

Given an integer array

Input

Several test cases(about

Output

For each cases, please output an integer in a line as the answer.

Sample Input

      3 2 1 2 2 3 2 1 2 3 

Sample Output

2 3

题解：让求一个数列中长度为k的LIS数列的种数（指的数组下标）；所以想到用dp，二维dp，dp[i][j]其中i指的是长度，j指的是以j结束的数；所以可以列出状态转移方程；

dp[x][i]=dp[x-1][j]+dp[x][i];每当if(m[i]>m[j])时开始从2到n遍历；由于数量太大，所以要用到高精度。。。

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 #define mem(x,y) memset(x,y,sizeof(x)) 8 typedef long long LL; 9 struct BIGINT{10     int num[20],len;11     void init(int x){12         mem(this->num,0);13         this->num[0]=x;14         this->len=1;15     }16 };17 BIGINT operator + (BIGINT a,BIGINT b){18     BIGINT c;19     c.init(0);//c要记得初始化。。。 20     int len=max(a.len,b.len);21     for(int i=0;i
          
           1e8)c.num[i]-=1e8,c.num[i+1]++;24 if(c.num[len])len++;25 }c.len=len;26 return c;27 }28 void print(BIGINT a){29 for(int i=a.len-1;i>=0;i--){30 printf("%d",a.num[i]);31 }puts("");32 }33 BIGINT dp[110][110],ans;//以j结尾长度为i的个数 34 int m[110];35 int main(){36 int n,k;37 while(~scanf("%d%d",&n,&k)){38 for(int i=1;i<=n;i++)scanf("%d",m+i);39 mem(dp,0);40 for(int i=1;i<=n;i++)dp[1][i].init(1);41 for(int i=1;i<=n;i++)42 for(int j=1;j
           
            m[j]){44 for(int x=2;x<=n;x++){45 dp[x][i]=dp[x-1][j]+dp[x][i];46 }47 }48 ans.init(0);49 for(int i=1;i<=n;i++)ans=ans+dp[k][i];50 print(ans);51 }52 return 0;53 }

大神优化过的代码。。。好难懂。。。还没懂。。。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define ull unsigned long long#define ll long long#define N 100005#define BASE 13131int n,k;int a[105];struct Cbig{    int num[20],len;    void init(int x)    {        len=1;        num[0]=x;    }}dp[2][105],ans,c;Cbig add(Cbig &a,Cbig &b){    c.len=max(a.len,b.len);    c.num[0]=0;    for(int i=0;i
         
          =100000000)        {            c.num[i]-=100000000;            c.num[i+1]=1;        }    }    if(c.num[c.len]) c.len++;    return c;}void print(Cbig &a){    printf("%d",c.num[a.len-1]);    for(int i=a.len-2;i>=0;i--)        printf("%08d",a.num[i]);    puts("");}int main(){    //freopen("tt.in", "r", stdin);    while(cin>>n>>k)    {        for(int i=1;i<=n;i++) scanf("%d",&a[i]);        dp[0][0].init(1);        for(int i=1;i<=n;i++) dp[0][i].init(0);        int p=0,q=1;        for(int t=1;t<=k;t++)        {            p^=1;q^=1;            for(int i=0;i<=n;i++) dp[p][i].init(0);            for(int i=1;i<=n;i++)            {                for(int j=0;j