UVa1579-套娃问题

在 UVa 1579 - Matryoshkas 这道题目中，我们需要利用动态规划（DP）的方法来求解如何将给定的一系列套娃合并成最少数量的套娃组，同时保证每个套娃组内的套娃能够正确嵌套。

定义 f(i) 为前 i 个套娃合并成多个套娃组所需的最小操作次数。状态转移方程可以表示为：

f(i) = min(f(j) + dp(j+1, i))

其中，dp(j+1, i) 表示从第 j+1 个到第 i 个套娃合并成一个套娃组所需的最小代价。为了计算 dp(j+1, i)，我们需要进一步细化，即：

dp(j+1, i) = min(dp(j+1, k) + dp(k, i) + 操作数)

这里的“操作数”是指将两个区间 [l, k] 和 [k+1, r] 合并时的额外操作次数。具体来说，如果 m1 = min(l, k) 和 m2 = min(k+1, r)，则不需要打开的套娃数为该区间中小于 max(m1, m2) 的套娃数量。

以下是具体的代码实现：

#include 
#include 
#include 

#define N 500 + 10
#define inf 0x3fffffff

using namespace std;

int a[N], mx[N][N], mn[N][N], p[N][N];
int n;
int f1[N][N], f2[N];

struct node {
    int x, id;
    inline bool operator <(const node &a) const {
        return x = 1; i--) {
        for (int j = i + 1; j <= n; j++) {
            mx[i][j] = max(mx[i][j-1], a[j]);
            mn[i][j] = min(mn[i][j-1], a[j]);
            flag = 1;
            for (int k = j - 1; k >= i; k--) {
                if (a[k] == a[j]) {
                    flag = 0;
                    break;
                }
            }
            if (flag && p[i][j-1]) p[i][j] = 1;
        }
    }
}

int dp(int x, int y) {
    if (f1[x][y] <10000) return f1[x][y];
    if (x == y) return f1[x][y] = 0;
    int num;
    node t[N];
    for (int i = x; i <= y; i++) t[i-x+1].x = a[i], t[i-x+1].id = i;
    sort(t+1, t+1+y-x+1);
    for (int i = x; i  10000) printf("impossible\n");
    else printf("%d\n", f2[n]);
}

int main() {
    while (scanf("%d", &n) == 1) {
        init();
        solve();
    }
    return 0;
}

数组 p[i][j] 用于标记区间 [i, j] 是否存在重复元素，具体判断条件为 p[i][j] = (p[i][j-1] && a[j] != 任何 i 到 j-1 的数)。

参考链接：https://www.cnblogs.com/star-eternal/p/7754277.html