Description
看这道题的形式和数据范围，斜率优化其实已经很明显。
但是当我们想要写转移的时候却遇到了麻烦...
计算当前花费的时候需要用到上一阶段的所用时间
且这个所用时间与其花费并没有什么关系
要保证正确性只能写一个看起来非常不爽的二维DP
我们会想，之前加工的时间会影响到当前从而不好处理，那我们能不能让现在的时间去影响之前的结果呢？
答案是肯定的，我们可以将状态反过来定义。用f[i]表示i..n的费用和。
f[i]=f[j]+(s*t[i]-t[j])*F[i]
t[i]表示i..n零件加工时间和，F[i]表示i..n的零件权值和。
这样一来，问题就明朗许多了。可以用普通的斜率优化进行。
设i<j<k 设此时取j比k好，则列出不等式
f[j]+(t[i]-t[j])*F[i]<f[k]+(t[i]-t[k])*F[i]
化简得
F[i]>(f[j]-f[k])/(t[j]-t[k])
这是我们熟悉的斜率表达式。设它为g[j,k]
维护一个下凸的单调序列。
求解当前答案的时候，我们可以通过g来得知哪些点取来更优
很容易发现当维护好序列单调性时，（g[j,k]<F[i]）是满足00000011111的
也就是遇到的第一个1的位置时的j就是我们所要求的状态。
求解直接按照推出的方程式转移即可。
接着我们要把当前点加入，同时维护单调性。
代码十分短感觉很优美>_<
program poj1180;
const maxn=;
var i,head,tail,n,s:longint;
opt,dp,f,t:array[-..maxn]of int64; function g(x,y:longint):extended;
begin
exit((dp[x]-dp[y])/(t[x]-t[y]));
end; begin
readln(n);
readln(s);
for i:= to n do readln(t[i],f[i]);
for i:=n- downto do
begin
inc(t[i],t[i+]);
inc(f[i],f[i+]);
end;
t[n+]:=;f[n+]:=;
head:=;tail:=;opt[]:=n+;dp[n+]:=;
for i:=n downto do
begin
while (head<tail)and(g(opt[head+],opt[head])<f[i]) do inc(head);
dp[i]:=dp[opt[head]]+(s+t[i]-t[opt[head]])*f[i];
while (head<tail)and(g(opt[tail],opt[tail-])>g(i,opt[tail])) do dec(tail);
inc(tail);opt[tail]:=i;
end;
writeln(dp[]);
end.
Description
也是一道斜率优化的拓展题。首先我们可以非常熟练地推出斜率：
g[j,k]=(f[j]-s[j]+j*a[j]-(f[k]-s[k]+k*a[k]))/(a[j]-a[k])
推的过程大同小异这里就不详细列出了。
然后转移方程
f[i]=f[j]+s[i]-s[j]-(i-j)*a[j]
(a[j]=s[j+1])（为了形式更优美我们把下标换成j当然不换也没有什么关系）
这道题的问题有两个
其中一个是k要怎么控制？刚开始想了一个并不好的方法就是在求解的时候各种控制但是还要担心缩tail的时候会影响后面的答案...
其实只要从DP的角度考虑，将i点加入队列无非就是给i以后的点增加一个可转移的状态
那么只要保证当前在求i的时候，i-k+1..i-1的点不在单调队列里就行了
自然而然地想到了延迟入队这样问题就迎刃而解了
在上一道题中，保证每个零件的加工时间都是非负整数，因此表示前缀和的t数组数字各不相同
而这道题不一样，作为分母的a数组可能相同，所以斜率还要特判分母等于0的情况
刚开始就是这里出了错。返回值要根据分子的符号来决定是正无穷还是负无穷。
program poj3709;
const maxn=;INF=;
var t,test,n,k,head,tail,v,i:longint;
s,a,opt,f:array[-..maxn]of int64; function g(x,y:longint):extended;
begin
if a[x]<>a[y] then exit((f[x]-s[x]+x*a[x]-f[y]+s[y]-y*a[y])/(a[x]-a[y]));
if (f[x]-s[x]+x*a[x]-f[y]+s[y]-y*a[y])> then exit(INF) else exit(-INF);
//如果分子是正的就返回正无穷否则返回负无穷
end; begin
readln(test);
for t:= to test do
begin
readln(n,k);
for i:= to n do read(s[i]);s[n+]:=;
for i:= to n do a[i]:=s[i+];
for i:= to n do inc(s[i],s[i-]);
head:=;tail:=;opt[]:=;s[]:=;f[]:=;
for i:=k to n do
//这里我控制的目的是不要让<k的无用状态将head移向后面
begin
while (head<tail)and(g(opt[head+],opt[head])<i) do inc(head);
f[i]:=f[opt[head]]+(s[i]-s[opt[head]])-(i-opt[head])*a[opt[head]];
if i-k+>=k then
//为下一次作的准备，i+1的时候需要i+1-k的状态。而且显然<k的状态是不能被转移的
begin
while (head<tail)and(g(opt[tail],opt[tail-])>g(i-k+,opt[tail])) do dec(tail);
inc(tail);opt[tail]:=i-k+;
end;
end;
writeln(f[n]);
end;
end.