求助站外题
  • 板块学术版
  • 楼主zyxawa
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/9/29 17:36
  • 上次更新2023/10/27 09:32:59
查看原帖
求助站外题
673294
zyxawa楼主2022/9/29 17:36

给定一个周长为LL的圆,从一个点出发,有 nn个黑白熊雕像,编号为 11nn,第 i i个雕像在顺时针 xix_i 米处,如果你没有在 tit_i 秒内收集到这个黑白熊雕像,那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。

现在 JOI 君在这个点,他每一秒可以移动一米,并且他可以顺时针或者逆时针的移动。

JOI 君想问,他最多能收集到多少个黑白熊雕像?

本蒟蒻一直调不处理,一直输出nn,求调

#include<bits/stdc++.h>
using namespace std;
int n,L,ans,x[202],t[202],dp[202][202][202][2];
int main(){
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;i++) scanf("%d",&x[i]);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	memset(dp,0x3f,sizeof(dp));
	dp[0][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++){
				for(int p=0;p<=1;p++){
					if(p==0){
						dp[l+1][r][k+(dp[l][r][k][p]+x[l+1]-x[l]<t[l+1])][0]=min(dp[l+1][r][k+(dp[l][r][k][p]+x[l+1]-x[l]<t[l+1])][0],dp[l][r][k][p]+x[l+1]-x[l]);
						dp[l][r+1][k+(dp[l][r][k][p]+x[l]+L-x[n-r]<t[n-r])][1]=min(dp[l][r+1][k+(dp[l][r][k][p]+x[l]+L-x[n-r]<t[n-r])][1],dp[l][r][k][p]+x[l]+L-x[n-r]);
					}
					else{
						dp[l+1][r][k+(dp[l][r][k][p]+L-x[n-r+1]+x[l+1]<t[l+1])][0]=min(dp[l+1][r][k+(dp[l][r][k][p]+L-x[n-r+1]+x[l+1]<t[l+1])][0],dp[l][r][k][p]+L-x[n-r+1]+x[l+1]);
						dp[l][r+1][k+(dp[l][r][k][p]+x[n-r+1]-x[n-r]<t[n-r])][1]=min(dp[l][r+1][k+(dp[l][r][k][p]+x[n-r+1]-x[n-r]<t[n-r])][1],dp[l][r][k][p]+x[n-r+1]-x[n-r]);
					}
				}
			}
		}
	}
	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++){
			//	cout<<dp[l][r][k][0]<<" "<<dp[l][r][k][1]<<endl;
				for(int p=0;p<=1;p++){
					if(dp[l][r][k][p]!=0x3f3f3f3f) ans=max(ans,k);
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}
2022/9/29 17:36
加载中...