洛古 P1020 导弹拦截 N^2

第一问维护最长不升子序列,第二问维护最长上升子序列(根据Dilworth定理:偏序集的最少反链划分数等于最长链的长度

第一问中,f[i]表示以a[i]结尾的最长不升子序列的最长长度,枚举j (1~i-1) ,若a[j]>=a[i],则f[i]=max(f[i],f[j]+1);i(因为a[j]后面可以接下去一个a[i]了,所以是f[j]+1)

最长上升自己序列类似,把第一问的思路中的“>=”改为"<"(懒得写了owo)

代码(N^2做法哟):

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n=0,a[100010];
 4 int f1[100010],f2[100010],ans=-1;
 5 int main(){
 6     while(~scanf("%d",&a[++n]));
 7     n--;
 8     f1[1]=1;
 9     for(int i=2;i<=n;i++){
10         f1[i]=1;
11         for(int j=i-1;j>=1;j--){
12             if(a[j]>=a[i]){
13                 f1[i]=max(f1[i],f1[j]+1);
14             }
15         }
16         ans=max(ans,f1[i]);
17     }
18     f2[1]=1;
19     printf("%d\n",ans);
20     ans=-1;
21     for(int i=2;i<=n;i++){
22         f2[i]=1;
23         for(int j=i-1;j>=1;j--){
24             if(a[j]<a[i]){
25                 f2[i]=max(f2[i],f2[j]+1);
26             }
27         }
28         ans=max(ans,f2[i]);
29     }
30     printf("%d",ans);
31     return 0;
32 }

 

上一篇:Java知识点系列:包装类型的缓存


下一篇:题解 P1020 【导弹拦截】