目录

题目

CF607B Zuma

算法标签: 动态规划, 区间 d p dp dp

思路

数据范围 N = 500 N = 500 N=500, 算法时间复杂度来到 O ( n 3 ) O(n ^ 3) O(n3)也是可以通过, 因此可以定义状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示 i i i到 j j j全部消除需要的最小化费, 很显然 f [ i ] [ i ] = 1 f[i][i] = 1 f[i][i]=1, 枚举区间长度, 再枚举区间左端点, 计算得到区间右端点, 进行状态转移即可, 算法时间复杂度 O ( n 3 ) O(n ^ 3) O(n3)

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510;

int n, w[N];
int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i) f[i][i] = 1;
    for (int i = 1; i < n; ++i) f[i][i + 1] = 1 + (w[i] != w[i + 1]);

    for (int len = 3; len <= n; ++len) {
   
        for (int i = 1; i + len - 1 <= n; ++i) {
   
            int j = i + len - 1;
            if (w[i] == w[j]) f[i][j] = f[i + 1][j - 1];
            for (int k = i; k < j; ++k) {
   
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
            }
        }
    }

    int ans = f[1][n];
    cout << ans << "\n";
    return 0;
}

*警示后人

因为要统计 f [ i + 1 ] [ j − 1 ] f[i + 1][j - 1] f[i+1][j−1], 如果不提前处理 l e n = 2 len = 2 len=2的情况可能会导致 i + 1 > j − 1 i + 1 > j - 1 i+1>j−1, 就是错误的, 因此需要提前处理 l e n = 2 len = 2 len=2的情况, 从 l e n = 3 len = 3 len=3开始枚举长度, 计算状态转移