您其实可以封装一下求斜率的部分的
于己于人都有好处
by fanypcd @ 2022-06-15 23:01:24
您这样写极有可能出错
by fanypcd @ 2022-06-15 23:01:50
嗯，好的
但是好像这样写也没有错……？
by Danno0v0 @ 2022-06-15 23:02:46
@[Danno0v0](/user/167279) 我在尽量不改变您的原代码的基础上改了一份可以 AC 的，您可以参考一下。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Sum[1000001],n,k;
int deq[1000001],h,t;
int dp[1000001][2];
int f[300001][301];
#define X(x) (Sum[x])
#define Y(x) (dp[x][0] - Sum[x] * Sum[x])
#define calc(x, y) make_pair(Y(y) - Y(x), X(y) - X(x))
bool cmp(pair<int, int> a, pair<int, int> b) {return a.first * b.second < b.first * a.second;}
void print(int i, int j)
{
if(f[i][j]) print(f[i][j], j - 1);
printf("%d ", i);
return;
}
signed main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>Sum[i];
Sum[i]+=Sum[i-1];
}
for(int ChainsawKiller=1;ChainsawKiller<=k;ChainsawKiller++)
{
memset(deq,0,sizeof(deq));
deq[1]=0,h=t=1;
for(int i=1;i<=n;i++)
{
while(h<t&&!cmp(calc(deq[h], deq[h + 1]), make_pair(-Sum[i], 1)))
h++;
dp[i][1]=dp[deq[h]][0]+(Sum[i]-Sum[deq[h]])*Sum[deq[h]];
f[i][ChainsawKiller]=deq[h];
while(h<t&&cmp(calc(deq[t - 1], deq[t]), calc(deq[t], i)))
t--;
deq[++t]=i;
}
for(int i=1;i<=n;i++)
dp[i][0]=dp[i][1];
}
cout<<dp[n][1]<<endl;
print(f[n][k], k - 1);
}
/*
199890017
299840021
*/
```
by fanypcd @ 2022-06-15 23:23:32
@[Danno0v0](/user/167279) 还有您最后的输出方案似乎是反的，不知道您怎么过的样例
by fanypcd @ 2022-06-15 23:24:49
我睡觉去了，有事明天早上再回
by fanypcd @ 2022-06-15 23:26:11
@[违规用户名pbFH$J9W](/user/90027)
非常感谢
貌似好像是入队斜率写错了((
另外方案输出因为顺序无关所以怎么输都可以吧
总之谢谢
by Danno0v0 @ 2022-06-15 23:50:02