题目链接: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();
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)