dedecms网站后台模板,网络销售技巧,文化传播公司做网站宣传好吗,淘宝客网站需要备案Luogu Description 求一个长度为n的序列a的最长下降子序列的长度,以及这个长度的子序列种数,注意相同的几个子序列只能算作一个子序列. n5000,a[i]不超过long范围 Sol 求最长下降子序列的长度: 1.f[i]表示以a[i]结尾的最长下降子序列长度 2.f[i]表示以i结尾的最长下降子序列…Luogu Description 求一个长度为n的序列a的最长下降子序列的长度,以及这个长度的子序列种数,注意相同的几个子序列只能算作一个子序列. n5000,a[i]不超过long范围 Sol 求最长下降子序列的长度: 1.f[i]表示以a[i]结尾的最长下降子序列长度 2.f[i]表示以i结尾的最长下降子序列长度 第一种适用于n比较小的,第二种则适用于n大而a[i]小的,这题显然用第一种吧,而且第一种更方便计数 用num[i]表示以a[i]结尾的长度为f[i]的子序列个数 还需注意的是,这题要去重. 所以更新num[i]数组,j从1循环到i-1时,遇到a[i]a[j]f[i]f[j]的情况num[i]-num[j]就好了 因为,在这样的情况中,num[j]所记录的子序列一定也被包含在num[i]中 Code 1 #includeiostream2 #includecstdio3 #includecstring4 #define Rg register5 #define il inline6 #define db double7 #define ll long long8 #define mem(a,b) memset(a,b,sizeof(a));9 #define go(i,a,b) for(Rg int ia;ib;i)
10 #define yes(i,a,b) for(Rg int ia;ib;--i)
11 using namespace std;
12 il int read()
13 {
14 int x0,y1;char cgetchar();
15 while(c0||c9){if(c-)y-1;cgetchar();}
16 while(c0c9){x(x3)(x1)c-0;cgetchar();}
17 return x*y;
18 }
19 const int N5001;
20 int n,ans1,p[N],l[N];//price length
21 db ans2,nm[N];//number
22 int main()
23 {
24 nread();
25 go(i,1,n)p[i]read(),l[i]1;
26 go(i,1,n)
27 {
28 go(j,1,i-1)if(p[j]p[i])l[i]max(l[i],l[j]1);
29 if(l[i]1)nm[i]1;
30 go(j,1,i-1)
31 {
32 if(p[i]p[j]l[i]l[j])nm[i]-nm[j];
33 if(p[j]p[i]l[j]1l[i])nm[i]nm[j];
34 }
35 }
36 go(i,1,n)if(l[i]ans1)ans1l[i];
37 go(i,1,n)if(l[i]ans1)ans2nm[i];
38 printf(%d %.0lf\n,ans1,ans2);
39 return 0;
40 } View Code 转载于:https://www.cnblogs.com/forward777/p/11010126.html
