首页 > 代码库 > [noip2013 d2t2]花匠
[noip2013 d2t2]花匠
题意：给定一串数，求最多可留下多少个呈波浪状排列的数
对于30%：最最朴素的暴力
对于70%：考虑O(n2) dp
设f[i][1]为以第i个数为结尾的序列，满足条件A的最优解；f[i][2]为以第i个数为结尾的序列，满足条件B的最优解
题目给出的两个条件，其实为状态转移提供了思路
不难得出方程
f[i][1]=max(f[j][2]+1)(j<i,h[i]>h[j])
f[i][2]=max(f[j][1]+1)(j<i,h[i]<h[j])
初始f[i][1]=f[i][2]=1;
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<ctype.h>
5 using namespace std;
6 const int maxn=100100;
7 int f[maxn][3],h[maxn];
8 int read(){
9 int x=0;
10 char ch=getchar();
11 while (!isdigit(ch)) ch=getchar();
12 while (isdigit(ch)){
13 x=x*10+ch-‘0‘;
14 ch=getchar();
15 }
16 return x;
17 }
18 int main(){
19 int n=read();
20 for (int i=1;i<=n;i++){
21 h[i]=read();
22 f[i][1]=f[i][2]=1;
23 }
24 int ans=1;
25 for (int i=1;i<=n;i++){
26 for (int j=1;j<i;j++){
27 if (h[i]>h[j]) f[i][1]=max(f[i][1],f[j][2]+1);
28 if (h[i]<h[j]) f[i][2]=max(f[i][2],f[j][1]+1);
29 }
30 ans=max(ans,max(f[i][1],f[i][2]));
31 }
32 printf("%d\n",ans);
33 return 0;
34 }
然而这并不足以通过所有测试，n=10w的规模让我们考虑优化
观察可知 f数组是单调递增的，所以我们可以倒序查找，找到上一个有解的f就退出
亦可修改方程，每个点都保存此前的最优值，令i只和i-1有关
两种方法的时间均可视为O(n)级别，前者常数稍大些
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<ctype.h>
5 using namespace std;
6 const int maxn=100100;
7 int f[maxn][3],h[maxn];
8 int read(){
9 int x=0;
10 char ch=getchar();
11 while (!isdigit(ch)) ch=getchar();
12 while (isdigit(ch)){
13 x=x*10+ch-‘0‘;
14 ch=getchar();
15 }
16 return x;
17 }
18 int main(){
19 int n=read();
20 for (int i=1;i<=n;i++){
21 h[i]=read();
22 f[i][1]=f[i][2]=1;
23 }
24 int ans=1;
25 for (int i=1;i<=n;i++){
26 for (int j=i-1;j>0;j--){
27 if (h[i]>h[j]) f[i][1]=max(f[i][1],f[j][2]+1);
28 if (h[i]<h[j]) f[i][2]=max(f[i][2],f[j][1]+1);
29 if (f[i][1]!=1&&f[i][2]!=1) break;
30 }
31 }
32 printf("%d\n",max(f[n][1],f[n][2]));
33 return 0;
34 }
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<ctype.h>
5 using namespace std;
6 const int maxn=100100;
7 int f[maxn][3],h[maxn];
8 int read(){
9 int x=0;
10 char ch=getchar();
11 while (!isdigit(ch)) ch=getchar();
12 while (isdigit(ch)){
13 x=x*10+ch-‘0‘;
14 ch=getchar();
15 }
16 return x;
17 }
18 int main(){
19 int n=read();
20 for (int i=1;i<=n;i++){
21 h[i]=read();
22 f[i][1]=f[i][2]=1;
23 }
24 for (int i=2;i<=n;i++){
25 if (h[i]==h[i-1]) {
26 f[i][1]=f[i-1][1];
27 f[i][2]=f[i-1][2];
28 }
29 if (h[i]>h[i-1]){
30 f[i][1]=max(f[i-1][2]+1,f[i][1]);
31 f[i][2]=f[i-1][2];
32 }
33 if (h[i]<h[i-1]){
34 f[i][1]=f[i-1][1];
35 f[i][2]=max(f[i-1][1]+1,f[i][2]);
36 }
37 }
38 printf("%d\n",max(f[n][1],f[n][2]));
39 return 0;
40 }
还有一种更简洁的方法：对于一个单调序列中的所有点，可以缩为一个点，故只需统计原序列的拐点个数即可，也是O(n)
[noip2013 d2t2]花匠
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。