最优时间表问题 动态规划,最合理的时间表

算法：DP

分析：本题算法同迅速的冬日的任务一样，都是用f[i]来表示i分钟开始之后能获得的最大空闲时间，因此最后的n-f[1]即为最小工作时间。
            先是去寻找起始时间在i之后或等于i的，对于起始时间等于i的，那么就要不断更新取最大值。
            直到到起始时间位于i之后的第一个任务，如果它的下一个任务不起始于i，那么i就能获得一个空闲时间。

program sche;const maxn=10000;var n,k:longint; f,st,last:array [0..maxn] of longint; procedure init;var i:longint;begin readln(n,k); for i:=1 to k do readln(st[i],last[i]);end;procedure main;var i,j:longint;begin j:=k; for i:=n downto 1 do begin while (st[j]>=i) and (j>=1) do begin if st[j]=i then if f[i+last[j]]>f[i] then f[i]:=f[i+last[j]]; dec(j); end; if st[j+1]<>i then f[i]:=f[i+1]+1; end;end;begin assign(input,'sche.in'); reset(input); assign(output,'sche.out'); rewrite(output); init; main; writeln(n-f[1]); close(input); close(output);end.