样例最后一组不过
查看原帖
样例最后一组不过
816204
Light_LE楼主2024/6/21 18:49

样例最后一组为无解,可是这个程序输出 10

#include<iostream>
#define maxn 55
#define INF 100001
using namespace std;
int n,T,m1,m2,_case,t[maxn],a,b,dp[10010][maxn]/*dp[i][j]表示时刻 i 在车站 j 最少的等待时间 */;
bool has_train[10010][maxn][2]/*has_train[i][j][0]表示时刻 i 在车站 j 是否有向左的列车,[1]为向右*/; 
int main(){
	//freopen("in.txt","r",stdin);
	std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	while(cin>>n && n){
		cin>>T;
		for(int i=1;i<=n-1;i++){
			cin>>t[i];
		}
		cin>>m1;
		for(int i=1;i<=m1;i++){
			cin>>a;
			
			int sum=a;
			for(int j=1;j<=n;j++){
				has_train[sum][j][1]=1;
				sum+=t[j];
			}
		}
		cin>>m2;
		for(int i=1;i<=m2;i++){
			cin>>b;
			
			int sum=b;
			for(int j=n;j>=1;j--){
				has_train[sum][j][0]=1;
				sum+=t[j-1];
			}
		}
		
		for(int i=1;i<=n-1;i++){
			dp[T][i]=INF;
		}
		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>1&&has_train[i][j][0]&&i+t[j-1]<=T){//left
					dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);
				}
				if(j<n&&has_train[i][j][1]&&i+t[j]<=T){//right
					dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
				}
			}
		}
		
		cout<<"Case Number "<<++_case<<": ";
		if(dp[0][1]>=INF){
			cout<<"impossible"<<endl;
		}
		else{
			cout<<dp[0][1]<<endl;
		}
	}
	return 0;
}
2024/6/21 18:49
加载中...