P6879 [JOI 2020 Final] スタンプラリー 3

代码在第 $47$ 个点出错了。找到一组大小为$30$的hack数据

30 30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
17 28 13 4 20 5 29 28 20 30 16 22 27 28 8 8 11 22 6 8 3 27 19 8 0 21 0 24 18 30

正确答案输出：

17

而我的代码输出

16

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
inline int read()
{
	char ch; int res=0;
	ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		res=res*10+ch-'0';
		ch=getchar();
	}
	return res;
}
inline void write(int x)
{
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
const int N=205;
const int INF=1e9;
int n,l,a[N<<1],t[N<<1];
struct Node{
	int t,ans;
}dp[N<<1][N<<1][2];
signed main()
{
	n=read(); l=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		a[i+n]=a[i];
	}
	for(int i=1;i<=n;i++)
	{
		t[i]=read();
		t[i+n]=t[i];
	}
	for(int i=1;i<=n+1;i++)
		for(int j=1;j<=n;j++)
			for(int k=0;k<=1;k++)
			{
				dp[j][j+i-1][k].ans=0;
				dp[j][j+i-1][k].t=INF*INF;
			}
	for(int i=1;i<=n;i++)
	{
		if(a[i]<=t[i]||(l-a[i])<=t[i])
		{
			dp[i][i][0].ans=1; dp[i][i][0].t=min(a[i],l-a[i]);
			dp[i][i][1].ans=1; dp[i][i][1].t=min(a[i],l-a[i]);
			dp[i+n][i+n][0].ans=1; dp[i+n][i+n][0].t=min(a[i],l-a[i]);
			dp[i+n][i+n][1].ans=1; dp[i+n][i+n][1].t=min(a[i],l-a[i]);
		}
	}
	int k;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			k=j+i-1;
			for(int p=j;p<k;p++)
			{
				if(dp[j][p][1].t+((a[k]-a[p]>=0)?(a[k]-a[p]):(a[k]+l-a[p]))<=t[k])
				{
					if(dp[j][p][1].ans+1>dp[j][k][1].ans)
					{
						dp[j][k][1].ans=dp[j][p][1].ans+1;
						dp[j][k][1].t=dp[j][p][1].t+((a[k]-a[p]>=0)?(a[k]-a[p]):(a[k]+l-a[p]));
					}else if(dp[j][p][1].ans+1==dp[j][k][1].ans)
					{
						dp[j][k][1].t=min(dp[j][k][1].t,dp[j][p][1].t+((a[k]-a[p]>=0)?(a[k]-a[p]):(a[k]+l-a[p])));
					}
				}
				if(dp[j][p][0].t+((a[k]-a[j]>=0)?(a[k]-a[j]):(a[k]+l-a[j]))<=t[k])
				{
					if(dp[j][p][0].ans+1>dp[j][k][1].ans)
					{
						dp[j][k][1].ans=dp[j][p][0].ans+1;
						dp[j][k][1].t=dp[j][p][0].t+((a[k]-a[j]>=0)?(a[k]-a[j]):(a[k]+l-a[j]));
					}else if(dp[j][p][0].ans+1==dp[j][k][1].ans)
					{
						dp[j][k][1].t=min(dp[j][k][1].t,dp[j][p][0].t+((a[k]-a[j]>=0)?(a[k]-a[j]):(a[k]+l-a[j])));
					}
				}
			}
			for(int p=k;p>j;p--)
			{
				if(dp[p][k][0].t+((a[p]-a[j]>=0)?(a[p]-a[j]):(a[p]+l-a[j]))<=t[j])
				{
					if(dp[p][k][0].ans+1>dp[j][k][0].ans)
					{
						dp[j][k][0].ans=dp[p][k][0].ans+1;
						dp[j][k][0].t=dp[p][k][0].t+((a[p]-a[j]>=0)?(a[p]-a[j]):(a[p]+l-a[j]));
					}else if(dp[p][k][0].ans+1==dp[j][k][0].ans)
					{
						dp[j][k][0].t=min(dp[j][k][0].t,dp[p][k][0].t+((a[p]-a[j]>=0)?(a[p]-a[j]):(a[p]+l-a[j])));
					}
				}
				if(dp[p][k][1].t+((a[k]-a[j]>=0)?(a[k]-a[j]):(a[k]+l-a[j]))<=t[j])
				{
					if(dp[p][k][1].ans+1>dp[j][k][0].ans)
					{
						dp[j][k][0].ans=dp[p][k][1].ans+1;
						dp[j][k][0].t=dp[p][k][1].t+((a[k]-a[j]>=0)?(a[k]-a[j]):(a[k]+l-a[j]));
					}else if(dp[p][k][1].ans+1==dp[j][k][0].ans)
					{
						dp[j][k][0].t=min(dp[j][k][0].t,dp[p][k][1].t+((a[k]-a[j]>=0)?(a[k]-a[j]):(a[k]+l-a[j])));
					}
				}
			}
		}
		for(int j=1;j<=n;j++)
		{
			k=j+i-1;
			if(k+n>2*n) continue;
			dp[j+n][k+n][0]=dp[j][k][0];
			dp[j+n][k+n][1]=dp[j][k][1];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			ans=max(ans,dp[j][j+i-1][0].ans);
			ans=max(ans,dp[j][j+i-1][1].ans);
		}
	write(ans); putchar('\n');
	return 0;
}