tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

PKU2134 Traffic Lights

ようやく通った… 100人目のACです。

問題文にかかれていない注意点:
・最初は速度が0なので、動けるようになるまで1秒かかります。すなわち開始から1秒後はかならず場所0にいます。
・最後は速度1で入ってきてもゴール地点で0になるので大丈夫です。
・最後の地点にある信号は無視できます。

みんなBFSみたいなことしてるけどDPで十分。

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[1210][120][14];
char str[2];
int tg[120];
int tr[120];
int tc[120];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	dp[0][0][0]=1;
	for(int i=0;i<b;i++){
		int p,q,r,t;
		scanf("%d%d%d%s%d",&p,&q,&r,str,&t);
		if(str[0]=='R')t+=q;
		tg[p]=q;
		tr[p]=r;
		tc[p]=t;
	}
	for(int i=0;i<1202;i++){
		for(int j=0;j<a;j++){
			if(tg[j]==0||(tc[j]+i)%(tg[j]+tr[j])<tg[j]){
				for(int k=0;k<13;k++){
					dp[i+1][j+k][k+1]|=dp[i][j][k];
					dp[i+1][j+k][k]|=dp[i][j][k];
					if(k)dp[i+1][j+k][k-1]|=dp[i][j][k];
					if(tg[j+k]!=0&&(tc[j+k]+i)%(tg[j+k]+tr[j+k])>=tg[j+k])break;
				}
			}else{
				dp[i+1][j][0]|=dp[i][j][0];
				dp[i+1][j][1]|=dp[i][j][0];
			}
		}
	}
	for(int i=0;i<1203;i++){
		if(dp[i][a][0]){
			printf("%d\n",i);
			break;
		}
	}
}

これでUSACO残り7問。