玄关,求助
查看原帖
玄关,求助
758200
_LDX_WWS_楼主2024/7/11 09:01
#include<bits/stdc++.h>
using namespace std;
const long long N=210,inf=1e15;
long long n,L,x[N],y[N],dp[N][N][N][2]; //左l个 右r个 获得k个 0 顺 1 逆 
int main(){
	cin>>n>>L;
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=n;i++) cin>>y[i];
	for(int i=0;i<=n;i++)
	for(int j=0;j<=n;j++)
	for(int k=0;k<=n;k++)
	dp[i][j][k][0]=dp[i][j][k][1]=inf;
	dp[0][0][0][0]=dp[0][0][0][1]=0;
	for(int l=0;l<=n;l++){
		for(int r=0;r<=n;r++){
			if(l+r>=n) break;
			for(int k=0;k<=n;k++){ 
				long long tmp=dp[l][r][k][0];
				if(tmp<inf){
					if(x[r+1]-x[r]+tmp<=y[r+1])
					dp[l][r+1][k+1][0]=min(dp[l][r+1][k+1][0],x[r+1]-x[r]+tmp);
					else
					dp[l][r+1][k][0]=min(dp[l][r+1][k][0],x[r+1]-x[r]+tmp);
					
					if(L-x[n-l]+x[r]+tmp<=y[n-l])
					dp[l+1][r][k+1][1]=min(dp[l][r+1][k+1][1],L-x[n-l]+x[r]+tmp);
					else
					dp[l+1][r][k][1]=min(dp[l][r+1][k][1],L-x[n-l]+x[r]+tmp);
				}
				tmp=dp[l][r][k][1];
				if(tmp<inf){
					if(x[n-l+1]-x[n-l]+tmp<=y[n-l])
					dp[l+1][r][k+1][1]=min(dp[l+1][r][k+1][1],x[n-l+1]-x[n-l]+tmp);
					else
					dp[l+1][r][k][1]=min(dp[l+1][r][k][1],x[n-l+1]-x[n-l]+tmp);
					
					if(L-x[n-l+1]+x[r+1]+tmp<=y[r+1])
					dp[l][r+1][k+1][0]=min(dp[l][r+1][k+1][0],L-x[n-l+1]+x[r+1]+tmp);
					else
					dp[l][r+1][k][0]=min(dp[l][r+1][k][0],L-x[n-l+1]+x[r+1]+tmp);
				}
			}
		}
	} 
	long long ans=0;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(long long k=0;k<=n;k++){
				if(min(dp[i][j][k][0],dp[i][j][k][1])!=inf) ans=max(ans,k);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
} 
2024/7/11 09:01
加载中...