RQNOJ 201 奥运大包围:LIS + 拼链成环

RQNOJ 201 奥运大包围:LIS + 拼链成环,第1张

RQNOJ 201 奥运大包围:LIS + 拼链成环

题目链接:https://www.rqnoj.cn/problem/201

题意:

  开始时n(n<=1000)个人手拉手围成一个圈。


  后来这些人中的一些按顺序向里面出圈形成一个新圈。


从而使原圈形成一个从高到低,最低与最高连接的圈。


  新圈重复相同的 *** 作,直到没有人要出圈为止。


  问最少要形成多少个这样的圈。


题解:

  (1)拼链成环:

    对于一个环,可以用两条由环拆开的链拼在一起表示。


    例如:有一个环为"1,2,3,4"(1和4连在一起),则可以表示为"1,2,3,4,1,2,3"。


       每一次从不同位置遍历环时,只需要枚举前n个点作为起点,向后遍历n个即可。


  (2)转化问题:

    原题可以变成:求最少有几个相互不重叠的严格下降子序列,能够将最初的环完全覆盖。


  (3)设计算法:

    首先有一个定理:下降子序列的个数 = 最长非降子序列的长度

    那么此题跟NOIP拦截导d的第二问就一模一样了。


    所以枚举每个起点,求一下最小的LIS(非降)就好啦。


    因为n<=1000,所以求LIS要用nlogn的方法。


总复杂度O(N^2*logn)。


AC Code:

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 2005
#define INF 10000000 using namespace std; int n;
int ans;
int a[MAX_N];
int d[MAX_N]; void read()
{
cin>>n;
for(int i=;i<n;i++)
{
cin>>a[i];
a[n+i]=a[i];
}
} int cal_lis(int *a)
{
int len=;
d[]=a[];
for(int i=;i<n;i++)
{
if(a[i]>=d[len])
{
d[++len]=a[i];
}
else
{
int lef=;
int rig=len;
while(rig-lef>)
{
int mid=(lef+rig)/;
if(a[i]>=d[mid]) lef=mid;
else rig=mid;
}
int res;
if(a[i]>=d[rig]) res=rig;
else if(a[i]>=d[lef]) res=lef;
else res=;
d[res+]=min(d[res+],a[i]);
}
}
return len;
} void solve()
{
ans=INF;
for(int i=;i<n;i++)
{
ans=min(ans,cal_lis(a+i));
}
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/zaji/585763.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-12
下一篇 2022-04-12

发表评论

登录后才能评论

评论列表(0条)

保存