题解 —— CF1675G Sorting Pancakes

· · 题解

难度不大，洛谷和cf评分都虚高。

对于这种问题，先简单看看有没有出现贪心技巧的可能。发现没有。再看看有没有什么似乎必定要做的操作。发现没有。再看数据范围——铁定dp了。

第一位肯定是枚举到第几个盒子。考虑到我们要保证他非严格单调递减，所以记录该个盒子放几个馅饼还是有必要的。然后又发现非严格单调递减性保证小于等于最后一个前面的都不用管了，肯定合法了。自然考虑二位dp。

然后发现有个问题：我们枚举到第 i 个盒子，考虑向前放几个馅饼时，会发现有可能我们向前一个放馅饼导致前一个比前前个馅饼多。所以这件事告诉我们还要加一位表示向后一个盒子放/取几个馅饼，这样就不会向前放馅饼导致问题了。

严谨的说， f_{i,j,k} 表示 [1,i] 号盒子中，盒子中的馅饼数非严格单调递减，并且第 i 个盒子有 j 个馅饼，向第 i+1 号盒子挪动 k 个馅饼的情况下，最小移动次数。如果 k 是负数则表示取走 |k| 个馅饼。

状态转移式自然也很明显：枚举上一个盒子有几个馅饼。

f_{i,j,k}=\min_{h \ge j} f_{i-1,h,j+k-a_i}+|k|

然后你会惊人的发现，这破玩意是 O(n\times m^3) 的，会被卡。然后你猜怎地？改式子？改转移？nonono。别的题解都是这样。我教你：是不是一大堆状态都是无效的？每次会从一大堆 \infty 中选最小值？所以啊，我们将第 i 的情况向 i+1 转移，如果当前状态是 \infty 直接 continue。这样就十分的能过了。毕竟想想看，难不成每次都有可能 j=m 或者 k=m？

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

const int N = 250;
int n, m;
int a[N+1];
int f[N+1][N+1][N*2+1];

int main() {
    // freopen("in", "r", stdin);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    memset(f, 0x3f, sizeof(f));
    f[0][N][0+N] = 0;
    a[0] = 114514;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= N; ++j) {
            for(int k = -N; k <= N; ++k) {
                if(f[i][j][k+N] > 1919810) continue;
                for(int l = 0, q = k+a[i+1]; l <= j && q > -N; ++l, --q) {
                    int &tmp = f[i+1][l][q+N];
                    tmp = min(tmp, f[i][j][k+N]+abs(q));
                }
            }
        }
    }
    int ans = 1919810;
    for(int i = 0; i <= N; ++i) ans = min(ans, f[n][i][0+N]);
    cout << ans << endl;
  return 0;
}