题目地址:https://codeforces.com/gym/101020/problem/D (洛谷无此题)
题很水,大意是找出一个数字序列中最长的公差为1的等差数列,非常基础的DP,但是我的代码在第三个数据处总是WA,各位能不能帮我找找问题
这是我的代码:
#include<bits/stdc++.h>
#define ll long long
#define re register int
#define MAXN 40005
using namespace std;
char *I,ibuf[(1<<21)|(1<<20)];
int filesize;
char getc()
{return I-ibuf<filesize?*I++:EOF;}
int read()
{
int ret=0,f=1;char ch=getc();
while(0<=ch&&('0'>ch||ch>'9')){if(ch=='-')f=-1;ch=getc();}
while('0'<=ch&&ch<='9'){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getc();}
return ret*f;
}
int n,T,f[MAXN],ans,cur;
int main()
{
filesize=fread(ibuf,1,(1<<21)|(1<<20),stdin);
I=ibuf;
T=read();
while(T--)
{
n=read();ans=0;
memset(f,0,sizeof(f));
for(re i=1;i<=n;i++)
{
cur=read();
f[cur]=f[cur-1]+1;
ans=max(ans,f[cur]);
}
printf("%d\n",ans);
}
return 0;
}
这是AC代码:
#include<bits/stdc++.h>
#define ll long long
#define re register int
using namespace std;
int n,T,f[20005],ans,cur;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);ans=0;
memset(f,0,sizeof(f));
for(re i=1;i<=n;i++)
{
scanf("%d",&cur);
f[cur]=f[cur-1]+1;
if(f[cur]>ans)ans=f[cur];
}
printf("%d\n",ans);
}
return 0;
}
改了半天实在找不出问题,也没有MLE,况且fread不可能比scanf慢,请各位dalao指教