题目描述
118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱员grant第1次顺序从流水线上取10个成品（如果一共不足10个，则全部取出），以后每一次把手中某种纯度的成品放进相应的箱子，然后再从流水线上顺序取一些成品，使手中保持10个成品（如果把剩下的全部取出不足10个，则全部取出），如果所有的成品都装进了箱子，那么grant的任务就完成了。
由于装箱是件非常累的事情，grant希望他能够以最少的装箱次数来完成他的任务，现在他请你编个程序帮助他。
输入输出格式
输入格式：
第1行为n（1<=n<=100），为成品的数量
以后n行，每行为一个大写字母A，B或C，表示成品的纯度。
输出格式：
仅一行，为grant需要的最少的装箱次数。
输入输出样例
输入样例#1：
11 A B C A B C A B C A B
输出样例#1：
3
用数组表示所有的状态，状态为当前拿到了第几个物品，同时现在手里有A类物品，B类物品，C类物品各几个，所以每次转移都是把一种东西放进去之后再取几件，然后就比较好写了
上代码：
#include<iostream>
#include<cstdio>
using namespace std;
int n,w[],f[][][][],t[],ans;
int read(){//read函数是对字符进行一下转变，变成数字
int x;char c=getchar();
while(c<'A'||c>'C') c=getchar();
x=c-'A'+;
return x;
} void dp(int cur,int nxt,int a,int b,int c,int k){//cur是当前状态的物品数，nxt转移后的状态的物品数，abc是三种物品在手中的数量，k是要放哪一种物品
int aa=a,bb=b,cc=c;
nxt=min(nxt,n);//不能超出
if(k==) aa=;
else if(k==) bb=;
else if(k==) cc=;
for(int i=cur+;i<=nxt;i++){
if(w[i]==) aa++;
else if(w[i]==) bb++;
else if(w[i]==) cc++;
}
f[nxt][aa][bb][cc]=min(f[nxt][aa][bb][cc],f[cur][a][b][c]+);//上一个状态的次数再多放一次
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
w[i]=read();
if(i<=){
t[w[i]]++;//先记录前十个物品三种各有几个
}
}
if(n<=){//小于十个就直接输出
for(int i=;i<=;i++){
ans+=(t[i]>?:);
}
printf("%d\n",ans);
return ;
} for(int i=;i<=n;i++){
for(int j=;j<=;j++){
for(int k=;k<=;k++){
for(int l=;l<=;l++){
f[i][j][k][l]=(<<);//初始化
}
}
}
}
f[][t[]][t[]][t[]]=;//初状态为零次， i<=10&&j<=t[1]&&k<=t[2]&&l<=t[3] 的状态不变为零，因为这些状态一定不是最优，所以不必初始化
for(int i=;i<=n;i++){
for(int j=;j<=;j++){
for(int k=;k<=;k++){
for(int l=;l<=;l++){
if(f[i][j][k][l]!=(<<)){//如果这个状态可以转移
if(j>){
dp(i,i+j,j,k,l,);//分别尝把每一种物品放回去进行状态进行转移
}
if(k>){
dp(i,i+k,j,k,l,);
}
if(l>){
dp(i,i+l,j,k,l,);
}
}
}
}
}
}
ans=(<<);
for(int j=;j<=;j++){
for(int k=;k<=;k++){
for(int l=;l<=;l++){
ans=min(ans,f[n][j][k][l]+(j>?:)+(k>?:)+(l>?:));//在所有已经取了n个物品的状态里取最小值
}
}
}
printf("%d\n",ans);
return ;
}