P2530 [SHOI2001] 化工厂装箱员

记状态f[i][a][b][c]表示到i这个位置,手里还剩下的a个A,b个B,c个C时装了几次箱.

那么状态转移(以A为例)：
if(ch[i]==A&&a)f[i][a][b][c]=f[i][a-1][b][c]
f[i][0][b][c]=min(f[i][0][b][c],f[i][a][b][c]+1)

答案既为f[n][0][0][0]

Code:

#include<bits/stdc++.h>
const int N=105;
const int M=11;
const int inf=1e9;
using namespace std;
int f[N][M][M][M];
void init()
{
    for(int i=0;i<N;i++)for(int a=0;a<M;a++)
    for(int b=0;b<M;b++)for(int c=0;c<M;c++)
    f[i][a][b][c]=inf;
}
int n;
char ch[N];
void work()
{
    cin>>n;
    init();
    for(int i=1;i<=n;i++)
    {
        cin>>ch[i];
    }
    f[0][0][0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int a=0;a<=10;a++)
        {
            for(int b=0;a+b<=10;b++)
            {
                for(int c=0;a+b+c<=10;c++)
                {
                    if(ch[i]=='A'&&a)f[i][a][b][c]=f[i-1][a-1][b][c];
                    if(ch[i]=='B'&&b)f[i][a][b][c]=f[i-1][a][b-1][c];
                    if(ch[i]=='C'&&c)f[i][a][b][c]=f[i-1][a][b][c-1];
                    f[i][0][b][c]=min(f[i][0][b][c],f[i][a][b][c]+1);
                    f[i][a][0][c]=min(f[i][a][0][c],f[i][a][b][c]+1);
                    f[i][a][b][0]=min(f[i][a][b][0],f[i][a][b][c]+1);
                }
            }
        }
    }
    printf("%d",f[n][0][0][0]);
}
int main()
{
    //freopen("P2530.in","r",stdin);
    //freopen("P2530.out","w",stdout);
    work();
    return 0;
}