[数据结构与算法]Arithmetic Operations（分类暴力dp）

Arithmetic Operations

[Link](Problem - E - Codeforces)

题意

给你一个数组$a$，每次操作可以选择一个$a_i$将其变成任意一个数$x$，问你最少操作多少次使之变成一个等差数列。

思路

? 不好判断修改哪几个数，但是哪些数不变比较好判断。我们可以枚举公差$d$，首先只考虑$d>=0$的情况对于$d<0$的情况，将原数组反转即可,对于每个$d$我们让$a_i?(i?1)?d$，相当于把偏移量减去，之后剩下的最多的就是我们要留下数，剩下的都是需要改变的。设$m=max(a_i)$，我们的公差不会超过这个数，例如$a_1,a_2,a_3$三个数$m=a_2$，如果$d<=m$则我们最多只需要改变$a_1,a_3$，若$d>m$则必须修改$a_1,a_2,a_3$。

? 但是这样枚举复杂度为$O(nm)$太高了，考虑分类对于$d<\sqrt{m}$的我们枚举$d$，复杂度为$O(n\sqrt{m})$。

? 对于$d\ge \sqrt{m}$情况，首先我们来证任意一个$a_i$最多可能和$a_{i+\sqrt{m}}$一起保留，假设$j>i+\sqrt{m}$，则$a_j?a_i\ge d\times \sqrt{m}>m$，由于$max(a_i)==m$因此显然不对，所以$i$和$j>i+\sqrt{m}$的数只能保留一个。由于要让一些数有相同的$d$，因此将$i\to j(j\le i+\sqrt{m})$连一条边，边权为$\frac{a_j?a_i}{j?i}=d$（如果可以整除），最多会有$n\sqrt{m}$条边，我们相当于要找最多的具有相同边权的边，由于是个拓扑图，可以直接用$f[i][j]:以i结尾的为d的边有多长$，转移即可，复杂度为$O(n\sqrt{m})$。

? 由于第二部分的图比较稀疏，因此实际上以小于$\sqrt{m}$来分类更优一些。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n, m, k;
int S = 200;
int a[N];
int b[N * 200];
int solve() {
    int res = 0;
    for (int d = 0; d < S; d ++) {
        for (int i = 0; i < n; i ++) {
            b[a[i] + d * (n - i)] ++;
            res = max(res, b[a[i] + d * (n - i)]);
        }
        for (int i = 0; i < n; i ++) 
            b[a[i] + d * (n - i)] --;
        
    }

    map<int, int> f[n + 1];

    for (int i = 0; i < n; i ++)
        for (int j = max(0, i - N / S); j < i; j ++) {
            int d = (a[i] - a[j]) / (j - i);
            int r = (a[i] - a[j]) % (j - i);
            if (d >= S && !r) {
                f[i][d] = max(f[i][d], f[j][d] + 1);
                res = max(res, f[i][d] + 1);
            }
        }

    return res;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    int ans = solve();
    reverse(a, a + n);
    ans = max(ans, solve());
    cout << n - ans << '\n';
    return 0;
}