【USACO】贝茜的晨练计划
【USACO】贝茜的晨练计划
滤菌器题⽬：
奶⽜们打算通过锻炼来培养⾃⼰的运动细胞，作为其中的⼀员，贝茜选择的运动⽅式是每天进⾏N(1 <= N <= 10,000)分钟的晨跑。 在每分钟的开始，贝茜会选择下⼀分钟是⽤来跑步还是休息。贝茜的体⼒限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这⼀分钟内跑D_i(1 <= D_i <= 1,000)⽶，并且她的疲劳度会增加1。不过，⽆论何时贝茜的疲劳度都不能超过M(1 <= M <= 500)。如果贝茜选择休息，那么她的疲劳度就会每分钟减少1，但她必须休息到疲劳度恢复到0为⽌。在疲劳度为0时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为0。还有，在N分钟的锻炼结束时，贝茜的疲劳度也必须恢复到0，否则她将没有⾜够的精⼒来对付这⼀整天中剩下的事情。 请你计算⼀下，贝茜最多能跑多少⽶。
输⼊：
第2..N+1⾏: 第i+1为1个整数：D_i
输出：
输出1个整数，表⽰在满⾜所有限制条件的情况下，贝茜能跑的最⼤距离。
⽐赛时神速想到DP
A了样例后就没理了
（⼀般DP题我都不抱有什么希望）
没想到分数下来
AC
线内钩子
我和我的⼩伙伴们都惊呆了...
我们⽤f[i,j]表⽰奶⽜跑了i分钟，疲劳值为j所能跑到的最远距离
如果j=0那么往前
把f[i,j]赋值为f[i-k,k](设k表⽰休息了k分钟）
j!=0的话
f[i,j]=max(f[i,j],f[i-1,j-1]+a[i]);
标程：
烧结线
var f:array[0..10000,0..500]of longint; d:array[0..10000]of longint;
n,m,i,j,k,l,s,x:longint;
function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; begin
readln(n,m);
for i:=1to n do有筋网
readln(d[i]);
for i:=1to n do
for j:=0to m do
begin
if j=0then
for k:=0to m do
if i-k>=0then
begin
f[i,j]:=max(f[i,j],f[i-k,k]);
f[i,j]:=max(f[i,j],f[i-k,0]);
end;
if j>0then
f[i,j]:=max(f[i-1,j-1]+d[i],f[i,j]);
开关柜除湿
end;
writeln(f[n,0]);双电源控制器
end.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议