求助
查看原帖
求助
542698
封禁用户楼主2023/6/11 21:52
#include<bits/stdc++.h>
using namespace std;
int t[55],M1,M2,dp[10015][10015];
bool train[55][10015][2];
int main()
{
	int n,T,num=0;
	while(cin>>n)
	{
		if(n==0)return 0;
		cin>>T;
		for(int i=0;i<55;i++)t[i]=0;
		for(int i=0;i<55;i++)
		{
			for(int j=0;j<10005;j++)
			{
				train[i][j][0]=0;
				train[i][j][1]=0;
			}
		}
		++num;
		for(int i=1;i<n;i++)cin>>t[i];
		cin>>M1;
		for(int i=1;i<=M1;i++)
		{
			int d;
			cin>>d;
			int num=d;
			for(int j=1;j<=n;j++)
			{
				train[num][j][0]=1;//right
				num+=t[j];
			}
		}
		cin>>M2;
		for(int i=1;i<=M2;i++)
		{
			int d;
			cin>>d;
			int num=d;
			for(int j=n;j>=1;j--)
			{
				train[num][j][1]=1;//left
				num+=t[j-1];
			}
		}
		for(int i=1;i<n;i++)dp[T][i]=0x3f3f3f3f;
		dp[T][n]=0;
		for(int i=T-1;i>=0;i--)
			for(int j=1;j<=n;j++)
			{
				dp[i][j]=dp[i+1][j]+1;
				if(j<n&&train[i][j][0]==1&&i+t[j]<=T)dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
				if(j>1&&train[i][j][1]==1&&i+t[j-1]<=T)dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);
			}
		if(dp[0][1]>=0x3f3f3f3f)cout<<"Case Number "<<num<<": impossible"<<endl;
		else cout<<"Case Number "<<num<<": "<<dp[0][1]<<endl;
	}
}//
2023/6/11 21:52
加载中...