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問。