WORIA

E. 找出最少动作数

https://acm.ecnu.edu.cn/contest/636/problem/E/

题意：一个堆栈中可以存 1 到 $n$ 的整数，定义某时刻堆栈的状态为此时堆栈中数值 1 到 $n$ 的个数 $\{cnt_1, cnt_2,\cdots, cnt_n\}$ 。初始时堆栈为空，给定 $m$ 个状态，要求仅使用 push，pop 操作，使堆栈依次遍历这 $m$ 个状态，并最终变为空，求最少操作次数。

区间dp

考虑可以把一些永远用不到数压在栈底。从一个状态转移到另一个状态时，可以有 $k_1$ 个数值1被压在栈底， $k_1$ 为状态 $L$ 到 $R$ 中数值 1 的个数的最小值，这些 $1$ 永远不会被用到，所以压在栈底是最优的。对于数值 $2,\cdots,n$ 也类似。

记一个虚拟状态，其具有状态区间 $L$ 到 $R$ 中各数值的个数的最小值，记为 $LR$ 的基础状态。记 $LR$ 的基础状态下各数值的个数之和为 $s[L][R]$ ，直接先统计出来。

$dp[L][R]$ 表示从 $LR$ 的基础状态变到 $L,L+1,\cdots,R$ 再变回 $LR$ 的基础状态，所需要的最少操作数。最终答案就是 $dp[1][m+1]$ 。

枚举区间 $[L,R]$ 的分割点，对于分割点 $i$ ，有

$dp[L][R] = dp[L][i] + dp[i+1][R]+2*(s[L][i]-s[L][R]+s[i+1][R]-s[L][R])\\$

即在区间 $[L, i]$ 和 $[i+1,R]$ 已经解决的条件下，要想合并这两个区间，必须先从 $LR$ 的基础状态操作到 $[L,i]$ 的基础状态，进行 $[L,i]$ 内部的操作，再操作回 $LR$ 的基础状态，再操作到 $[i+1,R]$ 的基础状态，进行 $[i+1,R]$ 内部的操作，再操作回 $LR$ 的基础状态。

#include <stdio.h>
#include <string.h>

#define N 105
#define INF 0x3f3f3f3f

int min(int a, int b){
    return a < b ? a : b;
}

int m, n;
int a[N][N], s[N][N], dp[N][N], mn[N];

int main(){
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)scanf("%d", &a[i][j]);
    for(int l = 1; l <= m + 1; l++){
        for(int i = 1; i <= n; i++)mn[i] = INF;
        for(int r = l; r <= m + 1; r++){
            for(int i = 1; i <= n; i++){
                mn[i] = min(mn[i], a[r][i]);
                s[l][r] += mn[i];
            }
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 1; i <= m + 1; i++)dp[i][i] = 0;
    for(int len = 2; len <= m + 1; len++){
        for(int l = 1; l <= m + 1 - len + 1; l++){
            int r = l + len - 1;
            for(int i = l; i < r; i++){
                dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r] + 2 * (s[l][i] - s[l][r] + s[i + 1][r] - s[l][r]));
            }
        }
    }
    printf("%d\n", dp[1][m + 1]);
    return 0;
}