不知道做出这道题是我能力的一个提升还是能力的回归。
DP。设f[i][j][k][l]是已经取了i个产品,现在手里还拿着j件A,k件B,l件C,最小的操作数。
然后状转方程乱搞啊
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
}long long f[][][][];
int s[][];
long long Max;
long long ans=0x7fffffff;
int main(){
memset(f,/,sizeof(f)); Max=f[][][][]; f[][][][]=;
int n=read();
for(int i=;i<=n;++i){
char c[];
scanf("%s",c+);
for(int j=;j<=;++j) s[j][i]=s[j][i-];
s[c[]-'A'+][i]++;
}
for(int i=;i<=n;++i)
for(int j=;j<=;++j)
for(int k=;k+j<=;++k)
for(int l=;l+k+j<=;++l){
if(f[i][j][k][l]==Max) continue;
if(j){
int a=s[][min(i+j,n)]-s[][i],b=s[][min(i+j,n)]-s[][i]+k,c=s[][min(i+j,n)]-s[][i]+l;
f[min(i+j,n)][a][b][c]=min(f[min(i+j,n)][a][b][c],f[i][j][k][l]+);
//printf("%lld ",f[min(i+j,n)][a][b][c]);
}
if(k){
int a=s[][min(i+k,n)]-s[][i]+j,b=s[][min(i+k,n)]-s[][i],c=s[][min(i+k,n)]-s[][i]+l;
f[min(i+k,n)][a][b][c]=min(f[min(i+k,n)][a][b][c],f[i][j][k][l]+);
//printf("%lld ",f[min(i+k,n)][a][b][c]);
}
if(l){
int a=s[][min(i+l,n)]-s[][i]+j,b=s[][min(i+l,n)]-s[][i]+k,c=s[][min(i+l,n)]-s[][i];
f[min(i+l,n)][a][b][c]=min(f[min(i+l,n)][a][b][c],f[i][j][k][l]+);
//printf("%lld ",f[min(i+l,n)][a][b][c]);
}
if(j+k+l<){
int q=-(j+k+l);
int a=s[][min(i+q,n)]-s[][i]+j,b=s[][min(i+q,n)]-s[][i]+k,c=s[][min(i+q,n)]-s[][i]+l;
f[min(i+q,n)][a][b][c]=min(f[min(i+q,n)][a][b][c],f[i][j][k][l]);
}
}
for(int i=;i<=;++i)
for(int j=;j+i<=;++j)
for(int k=;k+j+i<=;++k)
ans=min(ans,f[n][i][j][k]+(i>?:)+(j>?:)+(k>?:));
printf("%lld",ans);
return ;
}