AcWing 1017. 怪盗基德的滑翔翼
思路：相当于做两次LIS
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 120;
int t[N];//存数
int p[N];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
int temp=0;
int m;
scanf("%d",&m);
for(int j=0;j<m;j++){
scanf("%d",&t[j]);
}
//min
for(int j=0;j<m;j++){
p[j] = 1;
for(int s=0;s<j;s++){
if(t[s]>t[j]){
p[j] = max(p[j],p[s]+1);
}
}
temp = max(temp,p[j]);
}
//max
for(int j=0;j<m;j++){
p[j] = 1;
for(int s=0;s<j;s++){
if(t[s]<t[j]){
p[j] = max(p[j],p[s]+1);
}
}
temp = max(temp,p[j]);
}
printf("%d\n",temp);
}
return 0;
}
- 登山
思路：找已一点为尾的up序列，这点为首的up序列（需要两个方向）
#include <iostream>
#include <algorithm>
using namespace std;
int t;
int s[1005];
int m1[1005];
int m2[1005];
int main(){
scanf("%d",&t);
for(int i=0;i<t;i++){
scanf("%d",&s[i]);
m1[i] = 1;
m2[i] = 1;
}
for(int i=0;i<t;i++){
for(int j=0;j<i;j++){
//up
if(s[j]<s[i]) m1[i] = max(m1[i],m1[j]+1);
}
}
//下面这段从后往前，不能合入上面
for(int i=t-1;i>=0;i--){
for(int j=t-1;j>i;j--){
//down
if(s[j]<s[i]) m2[i] = max(m2[i],m2[j]+1);
}
}
int r = m1[0]+m2[0]-1;
for(int i=0;i<t;i++){
r = max(r,m1[i]+m2[i]-1);
}
printf("%d",r);
return 0;
}
合唱队形
和上题登山一样友好城市
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int,int> PII;
const int N = 5010;
int r[N],n;
int main(){
scanf("%d",&n);
vector<PII> c;
for(int i=0;i<n;i++){
int a,b;
scanf("%d %d",&a,&b);
c.push_back({a,b});
r[i] = 1;
}
sort(c.begin(),c.end());
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(c[i].second>c[j].second) r[i] = max(r[i],r[j]+1);
}
}
int re = r[0];
for(int i=0;i<n;i++){
re = max(re,r[i]);
}
printf("%d",re);
}
最大上升子序列和
就是将计长度换成了计总和拦截导弹（好题）
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行，输入导弹依次飞来的高度。
输出格式
第一行包含一个整数，表示最多能拦截的导弹数。
第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。
输入样例：
389 207 155 300 299 170 158 65
输出样例：
6
2
思路：贪心，最优方案之一为每次将当前数放在最小的序列后，做到尽量让末尾下降得慢
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N],b[N],c[N];
int main(){
n=0;
while(cin>>a[n]) n++;
int res = 0;
for(int i=0;i<n;i++){
b[i] = 1;
for(int j=0;j<i;j++){
if(a[i]<=a[j]) b[i] = max(b[i],b[j]+1);
}
res = max(res,b[i]);
}
cout<<res<<endl;
int num=0;
for(int i=0;i<n;i++){
int cmin=30010;
int sel;
bool f = false;
for(int j=0;j<num;j++){
if(a[i]<=c[j]&&cmin>c[j]){
f = true;
cmin = c[j];
sel = j;
}
}
if(!f){
c[num] = a[i];
num++;
}else{
c[sel] = a[i];
}
}
cout<<num;
return 0;
}
