SHOI2001化工厂装箱员——记忆化搜索

题目：https://www.luogu.org/problemnew/show/P2530

太弱了不会用DP，于是暴搜；

每次传进一个数组c记录当前状态各种物品有多少个，枚举取哪种物品，返回最小值，外加记忆化；

因为各种愚蠢小错误WA了好久。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,c[],a[],f[][][][],inf=;

char dc;

int ch(char c)

{

    if(c=='A')return ;

    if(c=='B')return ;

    if(c=='C')return ;

}

//void dfs(int c[],int now,int x)

//{

//    int c1=c[1],c2=c[2],c3=c[3];

////    if(f[now][c1][c2][c3])return;

////    cout<<c1<<c2<<c3;

////    cout<<x<<endl;

//    if(!c1&&!c2&&!c3)

//    {

//        ans=min(ans,x);

//        return;

//    }

//    int j;

//    for(int i=1;i<=3;i++)

//    {

//        if(!c[i])continue;//!

//        int k=c[i];

//        c[i]=0;

//        for(j=now+1;j<=now+k&&j<=n;j++)

//            c[a[j]]++;

//        f[now][c[1]][c[2]][c[3]]=min(f[now][c[1]][c[2]][c[3]],x+1);

//        dfs(c,j,f[now][c[1]][c[2]][c[3]]);

//        c[1]=c1;c[2]=c2;c[3]=c3;

//    }

//}

int dfs(int c[],int now)

{

    if(f[now][c[]][c[]][c[]])return f[now][c[]][c[]][c[]];

    if(!c[]&&!c[]&&!c[])return ;

    int ans=inf;

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

    {

        if(!c[i])continue;

        int t1=c[],t2=c[],t3=c[],j,t=c[i];

        c[i]=;

        for(j=now;j<now+t&&j<=n;j++)

            c[a[j]]++;

        ans=min(ans,dfs(c,j));

        c[]=t1;c[]=t2;c[]=t3;

    }

    ans++;//

    f[now][c[]][c[]][c[]]=ans;

    return ans;

}

int main()

{

    scanf("%d",&n);

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

    {

        cin>>dc;

        if(dc=='A')a[i]=;

        if(dc=='B')a[i]=;

        if(dc=='C')a[i]=;

    }

    int i;

    for(i=;i<=&&i<=n;i++)c[a[i]]++;//

    printf("%d",dfs(c,i));//

    return ;

}