题解：P11311 漫长的小纸带

· · 题解

P11311 漫长的小纸带 题解

题意

给定一个长为 n 数组 a，将他分成若干段，每段的代价为这一段数字个数的平方，求最小代价。

思路

看到分段、最小代价这些字眼，于是考虑 dp：

设 dp_i 表示 1 到 i 的最小代价，s_{i,\,j} 为 i 到 j 的不同数字个数。

考虑这个状态可以由那些状态得来，发现可以枚举 i 所在块的长度 k，此时 dp_i=dp_{i-k}+s_{i,\,j}^2，状态转移方程有了，便可 dp，复杂度 O(n^2)，能拿 32pts（卡常可卡到 48pts）

考虑怎么优化，我们发现当我们考虑 1 到 i 时，如果分成 i 块，则总代价为 i，所以不可能存在某一块的数字个数大于 \sqrt i，所以我们枚举 k 的时候，有用的 k 仅当：

于是我们可以改变枚举方法，令以 j 为右端的块，数字种类数为 i，块的左端点最左到 pre_{i,\,j}。这个东西的大小只有 n\sqrt n，也可以通过双指针 O(n\sqrt n) 求。

于是我们有了新的转移方程：

\large dp_{i,\,j}=\large \max_{j=1}^{\lfloor\sqrt i\rfloor}dp_{pre_{j,\,i}-1}+j^{2}

Code

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 200010;

int n, a[maxn], l, r, pre[490][maxn], sum, dp[maxn], ls[maxn], tot, t[maxn];
map <int, int> v;

void pu(int x) {//加入
    if (!(t[x]++)) {
        sum++;
    }
    return ;
}
void po(int x) {//删除
    if (!(--t[x])) {
        sum--;
    }
    return ;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;//读入
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ls[i] = a[i];
    }

    sort(ls + 1, ls + 1 + n);//本做法必须离散化，要不然双指针就TLE了
    ls[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (ls[i] != ls[i - 1]) {
            v[ls[i]] = ++tot;
        }
    }
    for (int i = 1; i <= n; i++) {
        a[i] = v[a[i]];
    }

    for (int i = 1; i <= sqrt(n); i++) {//双指针求pre
        l = 1, r = 0;
        sum = 0;
        for (int j = 1; j <= tot; j++) {
            t[j] = 0;
        }
        for (int j = 1; j <= n; j++) {
            pu(a[++r]);
            while (sum > i) po(a[l++]);
            pre[i][j] = l;
        }
    }

    dp[1] = 1;
    for (int i = 2; i <= n; i++) {//dp转移
        dp[i] = maxn;
        for (int j = 1; j <= sqrt(i); j++) {
            dp[i] = min(dp[pre[j][i] - 1] + j * j, dp[i]);
        }
    }

    cout << dp[n];//输出

    return 0;
}