首页 > 其他 > 详细

洛谷 P2362 围栏木桩

时间:2019-12-13 23:14:51      阅读:76      评论:0      收藏:0      [点我收藏+]

题目传送门

解题思路:

本题实质就是求最长上升子序列的长度和方案数。

AC代码:

 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 }

洛谷 P2362 围栏木桩

原文:https://www.cnblogs.com/lipeiyi520/p/12037468.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!