【题目大意】
韵哲君发现自己的面前有一行数字，当她正在琢磨应该干什么的时候，这时候，陈凡老师从天而降，走到了韵哲君的身边，低下头，对她耳语了几句，然后飘然而去。
陈凡老师说了什么呢，陈凡老师对韵哲君说了这些话：“还记得我传授给你的不下降子序列吗？你现在只要找出一定长度的不下降子序列的种数，你就完成任务了。”
你也来做做这个活动吧？
输入格式 Input Format
第一行有两个整数N(0<N<=200)，M(0<M<=20)；
N表示给出多少个整数，M表示给出的定长；
第二行有N个整数，对于每个数字(-10000<=T[i]<=10000)。
输出格式 Output Format
输出一个整数，在给出的数列中定长不下降子序列的种数。
样例输入 Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
样例输出 Sample Output
252
时间限制 Time Limitation
2s（对于高精度版）
【思路】
动态规划，设置数组f[i][j]表示以第i个数字为末位，长度为j的不下降子序列种类数。设置三重循环，第一重表示以第i个数字为末位，第二重j表示当前要取的不下降子序列长度，第三重k枚举这个不下降子序列的倒数第二个数字。如果a[i]≥a[k]，则f[i][j]=f[i][j]+f[k][j-1]。
要注意的是，最后输出结果不是f[n][m]，而是所有f[i][m]的累加！我因为这个一开始错了好久…
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=200+50; 7 struct node 8 { 9 int num[100]; 10 int len; 11 }; 12 int n,m; 13 int a[MAXN]; 14 node f[MAXN][MAXN/10]; 15 16 void init() 17 { 18 scanf("%d%d",&n,&m); 19 for (int i=0;i<n;i++) scanf("%d",&a[i]); 20 for (int i=0;i<n;i++) 21 for (int j=1;j<=m;j++) 22 { 23 memset(f[i][j].num,0,sizeof(f[i][j].num)); 24 if (j==1) 25 { 26 f[i][j].num[0]=1; 27 f[i][j].len=1; 28 } 29 else f[i][j].len=0; 30 } 31 } 32 33 void doadd(int a[100],int b[100],int &la,int lb) 34 { 35 int leng=max(la,lb); 36 int temp[100]; 37 memset(temp,0,sizeof(temp)); 38 for (int p=0;p<leng;p++) 39 { 40 temp[p]+=a[p]+b[p]; 41 /*由于是先进行进位的，这里不是将a[p]+b[p]赋值，而是累加在temp[p]上面*/ 42 temp[p+1]=temp[p]/10; 43 temp[p]=temp[p]%10; 44 } 45 if (temp[leng]>0) leng++; 46 la=leng; 47 for (int p=0;p<leng;p++) a[p]=temp[p]; 48 } 49 50 void dp() 51 { 52 for (int i=1;i<n;i++)/*以第i个数为末位*/ 53 for (int j=2;j<=min(i+1,m);j++)/*长度为j，只需取到i+1和m中较小的一个即可*/ 54 for (int k=j-2;k<i;k++)/*前一个数字为k,只需从能够取到j-1长度的那一位，即j-2开始*/ 55 if (a[i]>=a[k]) 56 doadd(f[i][j].num,f[k][j-1].num,f[i][j].len,f[k][j-1].len);/*f[i][j].num+=f[k][j-1].num*/ 57 } 58 59 void print() 60 { 61 int ans[100]; 62 memset(ans,0,sizeof(ans)); 63 int lans=0; 64 65 for (int i=m-1;i<n;i++) doadd(ans,f[i][m].num,lans,f[i][m].len); 66 /*不是直接输出f[n-1][m]，而是要将f[i][m]进行累加*/ 67 for (int i=lans-1;i>=0;i--) cout<<ans[i];cout<<endl; 68 } 69 70 int main() 71 { 72 freopen("mr360.in1","r",stdin); 73 freopen("mr360.ou1","w",stdout); 74 init(); 75 dp(); 76 print(); 77 return 0; 78 }