搜索
查看: 367|回复: 2
打印 上一主题 下一主题

最长不降序子列问题

[复制链接]
跳转到指定楼层
楼主
 楼主| 发表于 2018-7-4 10:42:02 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
15啊哈币
#include <bits/stdc++.h>
using namespace std;
int n,MAX=-55,dx=1;
int ben[1000];
struct shu
{
int xiabiao;
int zhi;       
};
struct shu x[1000];
void qk(int zuo,int you)
{
int i,j;
struct shu k,temp;
temp=x[zuo];
i=zuo;
j=you;
if(zuo>you)
return;
while(i!=j)
{
while(i<j && x[j].zhi>=x[zuo].zhi)
j--;
while(i<j && x[i].zhi<=x[zuo].zhi)
i++;
if(i<j)
{
k=x[i];
x[i]=x[j];
x[j]=k;
}
}
x[zuo]=x[i];
x[i]=temp;
qk(zuo,i-1);
qk(i+1,you);
return;
}
int max(int x,int y)
{
        if(x>y) return x;
        else return y;
}
int zhou(int x,int dai,int s)
{
        if(x>n)
        return dai;
        if(ben[x]>s)
        {
        max(zhou(x+1,dai+1,ben[x]),zhou(x+1,dai,s));
        }
        else x++;
   return zhou(x,dai,s);
}
int main()
{
        int i,j,s;
  scanf("%d",&n);
   for(i=1;i<=n;i++)
   {
                scanf("%d",&ben[i]);
                x[i].zhi=ben[i];
                x[i].xiabiao=i;
   }
   qk(1,n);
   for(i=1;i<=n;i++)
   {
        if(MAX>=n-i)
        continue;
        s=zhou(x[i].xiabiao,1,x[i].zhi);
   if(s>MAX);
   {
   MAX=s;
   }
   
        }
printf("%d",MAX);
return 0;
}
怎么不输出

沙发
发表于 2018-10-16 23:26:30 | 只看该作者
提示: 作者被禁止或删除 内容自动屏蔽
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

广播台
特别关注
快速回复 返回顶部 返回列表