自动搬运

查看原文

来自洛谷，原作者为

	Always **

搬运于2025-08-24 21:38:43，当前版本为作者最后更新于2018-08-31 09:42:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里提供一种新的思路:

状态:f[i][j][k][m] : 前i个物品 当前手中有j个"A" k个"B" m个"C"时的最小卸货次数

很明显对于第i个物品可以

1:)只取出来 暂时不装进去 前提就是当前手中货物数量<10

2:)取出来后 装进去 没有前提

所以转移方程就出来了:

f[i][j][k][m] = f[i-1][j-1][k][m] if(ob[i]=='A' && j)

f[i][j][k][m] = f[i-1][j][k-1][m] if(ob[i]=='B' && k)

f[i][j][k][m] = f[i-1][j][k][m-1] if(ob[i]=='C' && m)

以上三个均是 只取出来

f[i][0][k][m] = f[i][j][k][m] + 1 ;

f[i][j][0][m] = f[i][j][k][m] + 1 ;

f[i][j][k][0] = f[i][j][k][m] + 1 ;

这三个就是卸货啦qwq 还有一个大前提:j+k+m<=10

初值:f[0][0][0][0]=0 ; 其他均为**+oo**

目标:f[n][0][0][0]

还不懂就结合蒟蒻的代码看看

#pragma GCC optimize (2)
#include<bits/stdc++.h>
#define M 10005
#define rep(i , x , y) for(register int i = x ; i <= y ; ++i)
#define Rep(i , x , y) for(register int i = x ; i >= y ; --i)
using namespace std ;
int f[101][11][11][11] ;
//f[i][j][k][m] 表示前i个物品 当前手上有A j个 B k个 C m个 
int n ;
char obje[101] ;//存物品 
int main(){
	memset(f , 63 , sizeof f) ;//赋为inf 
	scanf("%d",&n) ;
	rep(i , 1 , n)cin >> obje[i] ;
	f[0][0][0][0] = 0 ;//初值 
	rep(i , 1 , n)rep(j , 0 , 10)rep(k , 0 , 10)rep(p , 0 , 10){
		if(j + k + p > 10)continue ;//手中物品不能超过10个 否则不处理 
		if(obje[i] == 'A' && j)//三个状态转移 都差不多(只装) 注意j,k,p得存在 
		f[i][j][k][p] = f[i - 1][j - 1][k][p] ;
		if(obje[i] == 'B' && k)
		f[i][j][k][p] = f[i - 1][j][k - 1][p] ;
		if(obje[i] == 'C' && p)
		f[i][j][k][p] = f[i - 1][j][k][p - 1] ;
		//这是卸货的转移 
		f[i][0][k][p] = min(f[i][0][k][p] , f[i][j][k][p] + 1) ;
		f[i][j][0][p] = min(f[i][j][0][p] , f[i][j][k][p] + 1) ;
		f[i][j][k][0] = min(f[i][j][k][0] , f[i][j][k][p] + 1) ;
	}
	printf("%d\n",f[n][0][0][0]) ;//终态 
	return 0 ;
}