题目链接 【AHOI2017/HNOI2017】礼物

<!--more-->

题解

其实修改亮度可以看做对其中一串手环整体加或者整体减去，所以只要在括号里加上就可以了。原来的式子就变长了这样：

我们继续拆一下式子

然后你会惊奇地发现，枚举了之后，除了最后一项之外都是常量。同时又是以最小化这个式子的值为目标的，所以只需要最大化就可以了。

现在把翻转，那么原来的式子就变成了这样

那你再把下标往左整体平移一下，

这不是卷积吗？那我们只需要做一遍再错位处理一下，取一个最大值就可以了。

思考下的本质，画一张图，就能理解如何错位了。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

const int MAXN = 1e6 + 7;
const double PI = std::acos(-1.0);

struct Complex {//自定义负数类
    double x, y;

    Complex(double _x = 0, double _y = 0) : x(_x), y(_y) {}

    Complex operator+(const Complex &a) const {
        return Complex(x + a.x, y + a.y);
    }

    Complex operator-(const Complex &a) const {
        return Complex(x - a.x, y - a.y);
    }

    Complex operator*(const Complex &a) const {
        return Complex(x * a.x - y * a.y, x * a.y + y * a.x);
    }
} a[MAXN], b[MAXN];

int sum1, sum2;
int len = 1, e = 0;
int r[MAXN], v[MAXN];

void fft(Complex *p, int type) {
    for (int i = 0; i < len; i++) {
        if (i < r[i]) std::swap(p[i], p[r[i]]);
    }
    for (int l = 1; l < len; l <<= 1) {
        Complex root(std::cos(PI / l), type * std::sin(PI / l));
        for (int i = 0; i < len; i += (l << 1)) {
            Complex t(1.0, 0.0);
            for (int j = 0; j < l; j++, t = t * root) {
                Complex x = p[i + j], y = t * p[i + l + j];
                p[i + j] = x + y;
                p[i + l + j] = x - y;
            }
        }
    }
}

int main(int argc, char *argv[]) {
    int n, m;
    scanf("%d %d", &n, &m); n--;
    for (int i = 0; i <= n; i++) {
        scanf("%lf", &a[i].x);
    }
    for (int i = 0; i <= n; i++) {
        scanf("%lf", &b[i].x);
    }
    for (int i = 0; i <= n; i++) {
        sum1 += a[i].x * a[i].x + b[i].x * b[i].x;
        sum2 += a[i].x - b[i].x;
    }
    int n2 = n + n;
    std::reverse(b, b + n + 1);
    while (len <= n2) len <<= 1, e++;
    for (int i = 0; i < len; i++) {
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (e - 1));
    }
    fft(a, 1), fft(b, 1);
    for (int i = 0; i <= len; i++) {
        a[i] = a[i] * b[i];
    }
    fft(a, -1);
    for (int i = 0; i <= n2; i++) {
        v[i] = (int)(a[i].x / len + 0.5);
    }
    int val = v[n];
    for (int i = 0; i <= n - 1; i++) {//错位处理
        if (val < v[i] + v[i + n + 1]) {
            val = v[i] + v[i + n + 1];
        }
    }
    val *= 2;
    int ans = 0x7fffffff;
    for (int i = -m; i <= m; i++) {
        ans = std::min(ans, sum2 * 2 * i + (n + 1) * i * i - val);
    }
    printf("%d\n", ans + sum1);
    return 0;
}