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

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

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

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

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

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,c[5],a[105],f[105][15][15][15],inf=100005;
char dc;
int ch(char c)
{
    if(c=='A')return 1;
    if(c=='B')return 2;
    if(c=='C')return 3;
}
//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[1]][c[2]][c[3]])return f[now][c[1]][c[2]][c[3]];
    if(!c[1]&&!c[2]&&!c[3])return 0;
    int ans=inf;
    for(int i=1;i<=3;i++)
    {
        if(!c[i])continue;
        int t1=c[1],t2=c[2],t3=c[3],j,t=c[i];
        c[i]=0;
        for(j=now;j<now+t&&j<=n;j++)
            c[a[j]]++;
        ans=min(ans,dfs(c,j));
        c[1]=t1;c[2]=t2;c[3]=t3;
    }
    ans++;//
    f[now][c[1]][c[2]][c[3]]=ans;
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>dc;
        if(dc=='A')a[i]=1;
        if(dc=='B')a[i]=2;
        if(dc=='C')a[i]=3;
    }
    int i;
    for(i=1;i<=10&&i<=n;i++)c[a[i]]++;//
    printf("%d",dfs(c,i));//
    return 0;
}

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

相关推荐