链接：Luogu-P1020
思路
第一问是裸的最长下降子序列问题。
第二问：
Dilworth 定理：
最长不降子序列长度，等于下降子序列划分数的最小值。
其对偶定理，即
最长下降子序列长度，等于不降子序列划分数的最小值。
同样成立。
我也不知道怎么证明的，要用到偏序集。但是因为和LIS问题有关，先记下来。
第二问需用到此定理。
最少需要的导弹系统数，实际上就等于最长不降子序列的长度。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN = 100;
int N,Ans1,Ans2,H[MAXN+10];
int op1[MAXN+10],op2[MAXN+10];
int main(){
while(scanf("%d",&H[N++])>0);
N--;
for(int i=0;i<N;i++)
op1[i]=op2[i]=1;
for(int i=0;i<N;i++)
for(int j=0;j<i;j++){
if(H[j]>H[i]) op1[i]=max(op1[i],op1[j]+1);
else op2[i]=max(op2[i],op2[j]+1);
}
for(int i=0;i<N;i++){
Ans1=max(Ans1,op1[i]);
Ans2=max(Ans2,op2[i]);
}
printf("%d\n%d\n",Ans1,Ans2);
}
