居然可以无知情况推导斜率优化
(话说洛谷此相似情况好多...指发明算法)
by zzw4257 @ 2020-08-18 22:26:34
@[zzw4257](/user/40629) 众所周知 你谷人均兔铃酱
by Spasmodic @ 2020-08-18 22:46:53
```cpp
#include<iostream>
#include<cstdio>
#define rg register
#define ll unsigned long long
using namespace std;
ll sum[50010],f[50010],q[50010];
int n,m,L;
ll Y(int j){return (f[j]+(sum[j]+j)*(sum[j]+j));}
ll X(int j){return (-2*(sum[j]+j));}
ll G(int i){return (i-1+sum[i]-L);}
ll DG(int i){return (G(i)*G(i));}
double T(int i,int j){return ((Y(i)-Y(j))/((X(i)-X(j))));}
int main()
{
scanf("%d%d",&n,&L);
for(rg int i=1;i<=n;i++){
int x;
scanf("%d",&x);
sum[i]=sum[i-1]+x;
}
int l=1,r=1;
for(rg int i=1;i<=n;i++){
while(l<r&&T(q[l],q[l+1])<G(i)) l++;
f[i]=Y(q[l])+DG(i)+G(i)*X(q[l]);
//printf("%lld %lld %lld %lld %lld\n",Y(q[l]),DG(i),G(i),X(q[l]),G(i)*X(q[l]));
while(l<r&&T(i,q[r-1])<T(q[r-1],q[r])){
swap(q[r-1],q[r]);
r--;
}
q[++r]=i;
}
for(rg int j=1;j<=n;j++)
printf("%lld ",f[j]);
return 0;
}
```
改了一下但还是不行。那我具体说一下我的意思吧。就是将这个方程展开之后得到$f_i$=$f_j$+$(i-1+sum[i-L]-L)^2$-2(i-l+sum[i]-L)(sum[j]+j)+$(sum[j]+j)^2$
设
ll Y(int j){return (f[j]+(sum[j]+j)*(sum[j]+j));}
ll X(int j){return (-2*(sum[j]+j));}
ll G(int i){return (i-1+sum[i]-L);}
ll DG(int i){return (G(i)*G(i));}
然后将j1和j2分别带入就可以得到一个有点像斜率的式子了。
by doughty @ 2020-08-19 11:53:45
@[happydef](/user/121027) 有不懂的地方吗
by doughty @ 2020-08-19 11:54:22
@[zzw4257](/user/40629) ？？不懂我的意思吗
by doughty @ 2020-08-19 11:55:06
```cpp
//斜率优化的第一题。
//具体做法：枚举每一个玩具，计算出他们的斜率，将永远不可能成为最优解的状态丢掉。
//还要把所有过期的状态一起丢掉。
//最后就是注意long long和队不能为空等问题。
//状态转移方程为：f[i]=min{f[j-1]+(i-j+sum[i]-sum[j-1]-L)^2}
//为了方便实现，同时把j改成j+1，得到：
// f[i]=min{f[j]+(i-j-1+sum[i]-sum[j]-L)^2}
#include<iostream>
#include<cstdio>
#define rg register
#define ll unsigned long long
using namespace std;
ll sum[50010],f[50010],q[50010];
int n,m,L;
ll Y(int j){return (f[j]+(sum[j]+j)*(sum[j]+j));}
ll X(int j){return (-2*(sum[j]+j));}
ll G(int i){return (i-1+sum[i]-L);}
ll DG(int i){return (G(i)*G(i));}
double T(int i,int j){return ((Y(i)-Y(j))/((X(i)-X(j))));}
int main()
{
scanf("%d%d",&n,&L);
for(rg int i=1;i<=n;i++){
int x;
scanf("%d",&x);
sum[i]=sum[i-1]+x;
}
int l=1,r=1;
for(rg int i=1;i<=n;i++){
while(l<r&&T(q[l],q[l+1])<G(i)) l++;
f[i]=Y(q[l])+DG(i)+G(i)*X(q[l]);
//printf("%lld %lld %lld %lld %lld\n",Y(q[l]),DG(i),G(i),X(q[l]),G(i)*X(q[l]));
while(l<r&&T(q[r-1],q[r])>T(q[r],i)){
//swap(q[r-1],q[r]);
r--;
}
q[++r]=i;
}
for(rg int j=1;j<=n;j++)
printf("%lld ",f[j]);
return 0;
}
```
这个是最新改的。
by doughty @ 2020-08-19 11:58:45
我问一下你，你求斜率既不是把除改成乘，又不是浮点数，怎么就直接下去整就行了？
by Wall_breaker @ 2020-09-01 22:31:56
@[doughty](/user/59824) 全WA
doge
by JohnFKennedy @ 2020-12-05 18:35:31