【BZOJ1049】【Luogu P2501】 [HAOI2006]数字序列 DP，结论，LIS

很有（\(bu\)）质（\(hui\)）量（\(xie\)）的一个题目。

第一问：求最少改变几个数能把一个随机序列变成单调上升序列。

\(Solution:\)似乎是一个结论？如果两个数\(A_i\)和\(A_j\)可以保留（\(i > j, A_i > A_j\)），即中间其他数都可以通过修改成为\([A_i, A_j]\)区间内的一个数，那么一定有\(i - j <= A_i - A_j\)，即\(A_i - i >= A_j - j\)。这个东西我们可以设为数列\(B\)，求一个最长不下降子序列就可以了。

（其实我中间智障了写成了最长上升子序列居然还有\(90ptshhhhh\)）

第二问：结论看这里。有了第一问的铺垫其实并不难想，但是问题在于可以有很多种最长不下降子序列，该怎么办？

我们考虑对答案\(DP\)，设\(f_x\)为前\(x\)个数有序化的最小代价（其中\(x\)一定是一个子序列内的点），然后来一发轻松愉快的\(DP\)。由于数据完全随机，所以可以剪枝过去。（虽然就是不随机恐怕也很难卡满就是了\(QwQ\)）

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 35000 + 5;

const int INF = 0x3f3f3f3f;

int n, A[N], B[N], Longest[N];

vector <int> q, G[N];

vector <int> :: iterator it;

int solve1 () {

    for (int i = 1; i <= n + 1; ++i) {

        if (q.empty () || B[i] >= q[q.size () - 1]) {

            q.push_back (B[i]); Longest[i] = q.size ();

        } else {

            it = upper_bound (q.begin (), q.end (), B[i]);

            *it = B[i]; Longest[i] = it - q.begin () + 1;

        }

        G[Longest[i]].push_back (i);

    }

    // Longest[i] : 以 i 结尾的最长不下降子序列

    return q.size () - 1; // 可以保留的数的个数

} 

int dp[N], hl[N], hr[N]; // hl[i] -> 从 l 到 i 都选择变成左端点值的代价, hr 同理 

int solve2 () {

    memset (dp, 0x3f, sizeof (dp));

    dp[0] = 0; G[0].push_back (0);

    for (int v = 1; v <= n + 1; ++v) {

        for (int i = 0; i < G[Longest[v] - 1].size (); ++i) {

            int u = G[Longest[v] - 1][i];

//			cout << "u = " << u << " v = " << v << endl;

            if (v < u || B[v] < B[u]) continue;

            hl[u] = hr[v] = 0;

            for (int k = u + 1; k < v; ++k) {

                hl[k] = hl[k - 1] + abs (B[k] - B[u]);

            }

            for (int k = v - 1; k > u; --k) {

                hr[k] = hr[k + 1] + abs (B[k] - B[v]);

            }

            for (int k = u; k < v; ++k) {

                dp[v] = min (dp[v], dp[u] + hl[k] + hr[k + 1]);

            }

        }

    }

    return dp[n + 1];

}

signed main () {

//	freopen ("data.in", "r", stdin);

//	freopen ("data.out", "w", stdout);

    cin >> n;

    B[0] = -INF, B[n + 1] = INF;

    for (int i = 1; i <= n; ++i) {

        cin >> A[i]; B[i] = A[i] - i;

    }

    cout << n - solve1 () << endl; // 对数列 B 做最长不下降子序列

    cout << solve2 () << endl; // ans

}

巴特西

【BZOJ1049】【Luogu P2501】 [HAOI2006]数字序列 DP，结论，LIS

最新文章

热门文章