// Offline solution of parking problem (Adam Meyerson, UCLA) // by dynamic programming in O(nk) time and O(n+k) space where // k is the number of permit types and n is the number of // not-necessarily-adjacent days when parking is needed. // BPW, 4/2006 // 9/11 - Converted to one-based arrays, consistent with notes 07 #include #include // These hold input int k,n; int *permitDays,*permitAmount; int *day; // DP arrays int *lag; // Keeps track of which day is this far back for DP int *prefixCost,*permitTypeUsed; void readInput() { int i; scanf("%d %d",&k,&n); permitDays=(int*) malloc((k+1)*sizeof(int)); permitAmount=(int*) malloc((k+1)*sizeof(int)); day=(int*) malloc((n+1)*sizeof(int)); if (!permitDays || !permitAmount || !permitDays) { printf("malloc failed %d\n",__LINE__); exit(0); } // The conditions required are important. for (i=1;i<=k;i++) scanf("%d %d",&permitDays[i],&permitAmount[i]); if (permitDays[1]<=0 || permitAmount[1]<=0) { printf("Illegal permit\n"); exit(0); } // The number of days and amounts for a permit type // are in ascending order to avoid useless permit types. for (i=2;i<=k;i++) if (permitDays[i-1]>=permitDays[i] || permitAmount[i-1]>=permitAmount[i]) { printf("Bad permit input\n"); exit(0); } // The days that a valid permit is needed are in // ascending order. Negative values are OK. day[0]=(-999999999); // Base case for (i=1;i<=n;i++) scanf("%d",&day[i]); for (i=1;i<=n;i++) if (day[i-1]>=day[i]) { printf("Bad day input\n"); exit(0); } } int main() { int i,j; int bestCost,bestJ,newCost; int permitBegin; int lagIndexSlow,permitTypeTrace,dayTrace; readInput(); lag=(int*) malloc((k+1)*sizeof(int)); prefixCost=(int*) malloc((n+1)*sizeof(int)); permitTypeUsed=(int*) malloc((n+1)*sizeof(int)); if (!lag || !prefixCost || !permitTypeUsed) { printf("malloc failed %d\n",__LINE__); exit(0); } // Lag values are explained below. for (i=1;i<=k;i++) lag[i]=0; // Initially each lag day is day[0] // Base case prefixCost[0]=0; // Loop to find an optimum strategy for the days through day[i] for (i=1;i<=n;i++) { printf("Processing day[%d]=%d\n",i,day[i]); bestCost=99999999; for (j=1;j<=k;j++) { //printf("Trying permit[%d] with days %d and amount %d\n", // j,permitDays[j],permitAmount[j]); // If a permit of type j ends on day[i], // lag[j] must point to the latest input day that // is earlier than the first day for this permit. // This loop advances the lag as long as the next day is // earlier than the permit period. This gives O(kn) overall while (day[lag[j]+1]=0 && day[lagIndexSlow]>=day[i]-permitDays[j]+1; lagIndexSlow--) ; if (lag[j]!=lagIndexSlow) printf("lag[%d]=%d not consistent with lagIndexSlow=%d\n", j,lag[j],lagIndexSlow); */ // Compute cost for solution that uses permit type j last. newCost=prefixCost[lag[j]]+permitAmount[j]; if (newCost0) { permitBegin=day[i]-permitDays[permitTypeUsed[i]]+1; printf("Permit type %d cost %d begin %d end %d\n", permitTypeUsed[i],permitAmount[permitTypeUsed[i]], permitBegin,day[i]); // Skip over days covered by permit for (i--; i>0 && day[i]>=permitBegin; i--) ; } printf("Backtrace using recomputation\n"); i=n; while (i>0) { // This loop computes permitBegin without using permitTypeUsed[i]. dayTrace=i-1; for (permitTypeTrace=1;permitTypeTrace<=k;permitTypeTrace++) { while (day[dayTrace]>=day[i]-permitDays[permitTypeTrace]+1) dayTrace--; if (prefixCost[i]==permitAmount[permitTypeTrace]+prefixCost[dayTrace]) break; } permitBegin=day[i]-permitDays[permitTypeTrace]+1; printf("Permit type %d cost %d begin %d end %d\n", permitTypeTrace,permitAmount[permitTypeTrace], permitBegin,day[i]); i=dayTrace; } free(lag); free(prefixCost); free(permitTypeUsed); free(permitDays); free(permitAmount); free(day); }