LG2530 「SHOI2001」化工厂装箱员 高维DP+记忆化搜索

问题描述

LG2530

题解

设\(opt[i][a][b][c][d]\)代表装到第\(i\)个后，第\(1,2,3\)手上分别还剩\(a,b,c\)个的最小操作数。

记忆化搜索即可。

启示：如果状态没想法，可以先写爆搜，确定状态。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

void read(int &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=100+7;
const int INF=0x3f3f3f3f;

int n,a[maxn];
int cnt[4];

int opt[maxn][11][11][11];
char c;

int dfs(int k[4],int step){
    if(opt[step][k[1]][k[2]][k[3]]) return opt[step][k[1]][k[2]][k[3]];
    if(!k[1]&&!k[2]&&!k[3]) return 0;
    int ret=INF;
    for(int i=1;i<=3;i++){
        if(!k[i]) continue;
        int aa=k[1],bb=k[2],cc=k[3],refe=k[i];
        k[i]=0;int j;
        for(j=step;j<=step+refe-1&&j<=n;j++) k[a[j]]++;
        ret=min(ret,dfs(k,j));
        k[1]=aa,k[2]=bb,k[3]=cc;
    }
    ++ret;
    return opt[step][k[1]][k[2]][k[3]]=ret;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c;a[i]=c-'A'+1;
    }
    if(n<=10){
        int ans=0;
        for(int i=1;i<=n;i++) cnt[a[i]]++;
        for(int i=1;i<=3;i++) if(cnt[i]) ++ans;
        printf("%d\n",ans);return 0;
    }
    for(int i=1;i<=10;i++){
        cnt[a[i]]++;
    }
    printf("%d\n",dfs(cnt,11));
    return 0;
}