【题解】SHOI2001化工厂装箱员

————传送：洛谷P2530

这道题目还是挺简单的，状态也容易想到。

数据范围非常的小，所以即便是很多维度，复杂度也完全可以接受。定义状态：dp[i][a][b][c]为手上的货物拿到第i个时三种物品分别有a, b, c个所用的最少次数。

状态转移就暴力枚举是放下a,b,c中的哪一个。

只不过需要特判一下n<10的情况。//再一次对自己丑陋的代码有点接受无能……

#include <bits/stdc++.h>

using namespace std;

#define maxn 102

#define INF 999999

int n, ans = INF, suma[maxn], sumb[maxn], sumc[maxn], dp[maxn][][][];

char c[maxn];

int min(int a, int b)

{

    if(b == -) return a;

    if(a == -) return b;

    return a < b ? a : b;

}

int trans(int x, int y, int aa, int bb, int cc)

{

    int a = suma[y] - suma[x], b = sumb[y] - sumb[x], c = sumc[y] - sumc[x];

    int sum = a + b + c + aa + bb + cc;

    bool done = false;

    if(sum - aa <= ) done = true, dp[y][a][b + bb][c + cc] = min(dp[x][aa][bb][cc] + , dp[y][a][b + bb][c + cc]);

    if(sum - bb <= ) done = true, dp[y][a + aa][b][c + cc] = min(dp[x][aa][bb][cc] + , dp[y][a + aa][b][c + cc]);

    if(sum - cc <= ) done = true, dp[y][a + aa][b + bb][c] = min(dp[x][aa][bb][cc] + , dp[y][a + aa][b + bb][c]);

    if(!done) return -;

    else return ;

}

int main()

{

    scanf("%d\n", &n);

    memset(dp, -, sizeof(dp));

    for(int i = ; i <= n; i ++)

    {

        cin >> c[i];

        suma[i] = suma[i - ];

        sumb[i] = sumb[i - ];

        sumc[i] = sumc[i - ];

        if(c[i] == 'A') suma[i] ++;

        else if(c[i] == 'B') sumb[i] ++;

        else sumc[i] ++;

    }

    if(n < )//特判

    {

        ans = ;

        if(suma[n]) ans ++;

        if(sumb[n]) ans ++;

        if(sumc[n]) ans ++;

        printf("%d\n", ans);

        return ;

    }

    dp[][suma[]][sumb[]][sumc[]] = ;

    for(int i = ; i <= n; i ++)

    {

        for(int aa = ; aa <= ; aa ++)

            for(int bb = ; bb <= ; bb ++)

                for(int cc = ; cc <= ; cc ++)

                {

                    if(dp[i][aa][bb][cc] == -) continue;

                    for(int j = i + ; j <= n; j ++)

                        if(trans(i, j, aa, bb, cc) == -) break;

                }

    }

    for(int aa = ; aa <= ; aa ++)

        for(int bb = ; bb <= ; bb ++)

            for(int cc = ; cc <= ; cc ++)

            {

                if(dp[n][aa][bb][cc] == -) continue;

                int tem = ;

                if(aa) tem ++;

                if(bb) tem ++;

                if(cc) tem ++;

                ans = min(ans, dp[n][aa][bb][cc] + tem);

            }

    printf("%d\n", ans);

    return ;

}