首页 > 其他分享 >CF1675G

CF1675G

时间:2022-10-28 21:35:35浏览次数:46  
标签:箱子 le min int 小球 CF1675G right

首先,可以感性地发现移动小球时出现负值不会影响最终答案,只要最终方案是非负的就行了。

所以,我们不妨规定,一个箱子只能从右边一个箱子拿小球,或者向右边一个箱子放小球。

设 \(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

相关文章