hdu 4749

时间:2023-03-09 16:51:12
hdu 4749

题目很简单,不过题意很难看懂。

就是给一个标准的大小关系的队列,从原队列中找出最多的匹配子队列,感觉就像一个KMP算法+贪心;

不过这个题可能数据有点水把,竟然只要判断相邻的关系就可以A掉;

代码:

 #include<cstdio>
#define maxn 100005
using namespace std;
int q[maxn],st[maxn],n,m,k; bool g(int a)
{
int i;
for(i=a; i<a+m-; i++)
{
if((q[i]==q[i+]&&st[i-a]==st[i-a+])||(q[i]<q[i+]&&st[i-a]<st[i-a+])||(q[i]>q[i+]&&st[i-a]>st[i-a+]))continue;
else break;
}
if(i==a+m-)return ;
return ;
} int main()
{
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
int ans=;
for(int i=; i<n; i++) scanf("%d",&q[i]);
for(int i=; i<m; i++) scanf("%d",&st[i]);
for(int i=; i<=n-m;) if(g(i))i=i+m,ans++;
else i++;
printf("%d\n",ans);
}
return ;
}