UVA 1025 A Spy in the Metro DP(二)
maxn],hasL[maxn][maxn]; void init() { memset(hasR,0,sizeof(hasR)); memset(hasL,0,sizeof(hasL)); memset(dp,63,sizeof(dp)); memset(t,0,sizeof(t)); memset(d1,0,sizeof(d1)); memset(d2,0,sizeof(d2)); } void getH() { for(int i=0;i
=1;j--) { time+=t[j+1]; hasL[time][j]=true; } } } int main() { int cas=1; while(scanf("%d",&n)!=EOF&&n) { init(); scanf("%d",&T); for(int i=2;i<=n;i++) scanf("%d",t+i); scanf("%d",&m1); for(int i=0;i
=0;i--) { for(int j=1;j<=n;j++) { dp[i][j]=dp[i+1][j]+1; if(j
1&&i+t[j]<=T&&hasL[i][j]) dp[i][j]=min(dp[i][j],dp[i+t[j]][j-1]); } } printf("Case Number %d: ",cas++); if(dp[0][1]>=INF) puts("impossible"); else printf("%d\n",dp[0][1]); } return 0; }