Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 220 Accepted Submission(s): 90
题解：让求一个数列中长度为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<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 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<len;i++){ 22 c.num[i]=a.num[i]+b.num[i]+c.num[i]; 23 if(c.num[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<i;j++) 43 if(m[i]>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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ull unsigned long long
#define ll long long
#define N 100005
#define BASE 13131
int 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<c.len;i++)
{
c.num[i+1]=0;
if(i<a.len) c.num[i]+=a.num[i];
if(i<b.len) c.num[i]+=b.num[i];
if(c.num[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<i;j++)
if(j==0||a[j]<a[i])
dp[p][i]=add(dp[p][i],dp[q][j]);
}
}
ans.init(0);
for(int i=1;i<=n;i++)
ans=add(ans,dp[p][i]);
print(ans);
}
return 0;
}
原文：http://www.cnblogs.com/handsomecui/p/4985454.html