最长严格上升子队列
题目链接: [ http://codevs.cn/problem/1576/ ]
题目
题目的意图已经很明显了，让我们在一个数组中找出一个最长的从小到大的子序列，想然我们可以对问题进行分化，我是怎么考虑的: 我们可以知道第一个数一定是一个长度子序列，那么在后面的数字只需要和他比较大小，比它晓得直接接在他的后面就行了，比如下面这三个数字3 1 23 成为长度为 1 的一串，但后面两个都比它小 1 成为长度为 1 的一串，2 比它大，所以得到长度为 2 的子序列 所以我们可以得到下面的状态转移方程:
f [ i ] = f [ j ] + 1;
代码
#include <cstdio>
using namespace std;
int n;
int a[5100],f[5100];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[1]=1;
for(int i=1;i<=n;i++){
int max=0;
for(int j=1;j<i;j++){
if(f[j]+1>max&&a[i]>a[j]){
max=f[j]+1;// 找出最大可能
}
}
f[i]=max;// 赋值给 f[i]
}
printf("%d",f[n]+1);// 别往了自己也是一个单位长度
}
合唱队形
题目链接: [http://codevs.cn/problem/1058/]
题目
定睛一看，是不是有点眼熟，是的，它也是最长子序列 不过这道题是要求在中间找一个“峰值”，使其左边的最长升序子序列与右边最长降序子序列的长度加起来最大 其中就可以很容易得出这样一种思路 - 我们在动归的同时，把每个数左边与右边存下来，这样一来，问题的思路就明朗了
代码
#include <cstdio>
using namespace std;
int n;
struct node {
int a,left,rig;
}a[110];
int main(){
int max;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].a);
for(int i=1;i<=n;i++){
max=0;
for(int j=1;j<i;j++){
if(a[j].a<a[i].a&&a[j].left+1>max){
max=a[j].left+1;
}
}
a[i].left=max;
}
for(int i=n;i>=1;i--){
max=0;
for(int j=n;j>i;j--){
if(a[j].a<a[i].a&&a[j].rig+1>max){
max=a[j].rig+1;
}
}
a[i].rig=max;
}
max=0;
for(int i=1;i<=n;i++){
if(a[i].left+a[i].rig+1>max) max=a[i].left+a[i].rig+1;
}
printf("%d",n-max);
}
拦截导弹
题目链接: [http://codevs.cn/problem/1044/]导弹拦截？拦截导弹？傻傻分不清楚 这道提的第一问就是一个简单的最长不降子序列，具体操作大家都明白 但是第二问求的是最少有几个最长不降子序列，这个就很艰难， 暴力当然会T，所以这题是有一个数学方法的，如果你想知道怎么求证，可以去bing 博主在这里只会讲讲这个定理
最少有几个不降子序列=最长上升序列的长度以此类推，我们还可以得到:
最少有几个不升子序列=最长下降子序列的长度 最少有几个上升子序列=最长不升序列的长度 最少有几个不降子序列=最长不降序列的长度那么这道题就很容易求解了，第一个输出最长不降子序列，第二个输出最长上升子序列
代码
#include <cstdio>
#include <cstring>
using namespace std;
int a[21],alen,max;
int f[21];
int main(){
while(scanf("%d",&a[alen++])!=EOF);
alen--;
for(int i=0;i<alen;i++){
for(int j=0;j<i;j++){
if(a[j]>=a[i]&&f[j]+1>f[i]) f[i]=f[j]+1;
}
}
for(int i=0;i<alen;i++) if(max<f[i]) max=f[i];
printf("%d\n",max+1);
memset(f,0,sizeof(f));
for(int i=0;i<alen;i++){
for(int j=0;j<i;j++){
if(a[j]<a[i]&&f[j]+1>f[i]) f[i]=f[j]+1;
}
}
max=0;
for(int i=0;i<alen;i++) if(max<f[i]) max=f[i];
printf("%d",max+1);
}