本题实质就是求最长上升子序列的长度和方案数。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 5 using namespace std; 6 7 int m,a[30],f[30],l[30],n; 8 9 int main() { 10 scanf("%d",&m); 11 while(m--) { 12 scanf("%d",&n); 13 for(int i = 1;i <= n; i++) { 14 scanf("%d",&a[i]); 15 f[i] = l[i] = 1; 16 } 17 f[25] = l[25] = 0; 18 for(int i = 1;i <= n; i++) { 19 for(int j = 1;j < i; j++) 20 if(a[i] >= a[j]) { 21 if(f[i] < f[j] + 1) 22 l[i] = l[j]; 23 if(f[i] == f[j] + 1) 24 l[i] += l[j]; 25 f[i] = max(f[i],f[j] + 1); 26 } 27 } 28 for(int i = 1;i <= n; i++) 29 if(f[25] < f[i]) 30 f[25] = f[i],l[25] = l[i]; 31 printf("%d %d\n",f[25],l[25]); 32 } 33 return 0; 34 }
原文:https://www.cnblogs.com/lipeiyi520/p/12037468.html