首先,可以感性地发现移动小球时出现负值不会影响最终答案,只要最终方案是非负的就行了。
所以,我们不妨规定,一个箱子只能从右边一个箱子拿小球,或者向右边一个箱子放小球。
设 \(f_{i,j,k}\) 表示前 \(i\) 个箱子,总共放 \(j\) 个小球,第 \(i\) 个盘子放 \(k\) 个小球的最小移动次数。
可以发现 \(f_{i,j,k}\) 能转移到 \(f_{i+1,j+p,p},p\le k\)。
设原来前 \(i\) 个箱子小球的总数量为 \(S_i\)。
考虑如何从 \(f_{i,j,k}\) 转移到 \(f_{i+1,j+p,p}\):由于我们每次转移小球都只和右边一个箱子有关,所以前 \(i\) 个箱子定好后的状态中,前 \(i+1\) 个箱子上的小球数之和依然是 \(S_{i+1}\)。
所以我们只需从第 \(i+2\) 个箱子里拿 \(j+p-S_{i+1}\) 个小球到第 \(i+1\) 个箱子上就行了(若拿负数个小球过来,等同于拿出去这么多个)。
则可以得出转移:\(f_{i+1,j+p,p}=\min(f_{i+1,j+p,p},f_{i,j,k}+\left|j+p-S_{i+1}\right|)\)。
初值为 \(f_{0,0,m}=0\),其余均为 \(\infty\),最终答案是 \(\min\limits_{0\le i\le m}\left\{f_{n,m,i}\right\}\)。
但是这样是 \(\mathcal O(nm^3)\) 的。
不难发现只要倒序枚举 \(k\),然后维护一个 \(mn=\min\limits_{k\le l\le m}\left\{f_{i,j,l}\right\}\) 就好了。
这样就能做到 \(\mathcal O(nm^2)\)。
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 255, inf = 0x3f3f3f3f;
int n, m;
int a[N], f[N][N][N];
int ans = inf;
void chkmin(int &a, int b) { if (a > b) a = b; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] += a[i - 1];
memset(f, 0x3f, sizeof f), f[0][0][m] = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j <= m; ++j) {
int mn = inf;
for (int k = m; ~k; --k) {
chkmin(mn, f[i][j][k]);
if (j + k <= m) chkmin(f[i + 1][j + k][k], mn + abs(j + k - a[i + 1]));
}
}
for (int i = 0; i <= m; ++i) chkmin(ans, f[n][m][i]);
printf("%d", ans);
return 0;
}
标签:箱子,le,min,int,小球,CF1675G,right
From: https://www.cnblogs.com/Kobe303/p/16837568.html