题解 P2530 【[SHOI2001]化工厂装箱员】

· · 题解

这里提供一种新的思路:

状态: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 ;
}