2018-12-19 19:45:36

40分：三方的DP不用解释了吧qwq

100分：四边形不等式（参见memset0巨佬的题解，蒟蒻我不会qwq）

101分：忘情水wqs二分

/*xxc 18/12/19       */
/*https://xcfubuki.cn*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define calc(x, y) (f[x] + w((x) + 1, y) + exc)
#define maxn 100005

using namespace std;
typedef long long LL;

int n, k, a[maxn], cnt[maxn], pre[maxn];
LL s[maxn], f[maxn], exc;

class jc
{
public:
int l, r, p;
} que[maxn];

{
char ch = getchar();
int ret = 0, f = 1;
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
ret = ret * 10 + ch - '0', ch = getchar();
return ret * f;
}

LL w(int l, int r)
{
if (l >= r)
return 0;
int mid = (r - l >> 1) + l;
LL res = a[mid] * (1ll * mid - l + 1) - (s[mid] - s[l - 1]);
res += (s[r] - s[mid - 1]) - (1ll * r - mid + 1) * a[mid];
return res;
}

int find(jc x, int s)
{
int L = x.l, R = x.r;
while (L <= R)
{
int mid = (R - L >> 1) + L;
if (calc(x.p, mid) > calc(s, mid))
R = mid - 1;
else
L = mid + 1;
}
return L;
}

int check()
{
int hed = 1, til = 0;
que[++til] = (jc){1, n, 0};
for (int i = 1; i <= n; ++i)
{
f[i] = calc(que[hed].p, i);
pre[i] = que[hed].p;
cnt[i] = cnt[que[hed].p] + 1;
int chs = -1;
while (hed <= til)
{
if (calc(i, que[til].l) < calc(que[til].p, que[til].l))
chs = que[til--].l;
else
{
int st = find(que[til], i);
if (st <= que[til].r)
chs = st, que[til].r = st - 1;
break;
}
}
if (chs != -1)
que[++til] = (jc){chs, n, i};
if (hed <= til)
{
que[hed].l++;
if (que[hed].l > que[hed].r)
hed++;
}
}
return cnt[n];
}

void output(int i)
{
if (0 == i)
return;
output(pre[i]);
printf("%d ", i);
}

int main()
{
for (int i = 1; i <= n; ++i)
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + 1ll * a[i];
LL L = 0, R = 1e6, res = 0;
while (L <= R)
{
LL mid = (R - L >> 1) + L;
exc = mid;
if (check() <= k)
res = mid, R = mid - 1;
else
L = mid + 1;
}
exc = res;
check();
printf("%lld\n", f[n] - k * res);
return 0;
}
• star
首页