题目描述
��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
题解:
水题哈,明显状态可以定义为f[i][j][k][g]为前i个,10个中A,B,C数量分别为j,k,g个
然后转移枚举清空哪一位再加上新产生的即可.
另外 这题还卡输入....
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 using namespace std; 8 const int N=105; 9 int s[N],f[N][12][12][12],sum[N][3]; 10 void work() 11 { 12 int n;char ch; 13 scanf("%d",&n); 14 for(int i=1;i<=n;i++){ 15 ch=getchar(); 16 while(ch>'C'||ch<'A')ch=getchar(); 17 s[i]=ch-'A'; 18 for(int j=0;j<=2;j++) 19 sum[i][j]=sum[i-1][j]+(s[i]==j); 20 } 21 if(n<=10){ 22 printf("%d ",(sum[n][0]>0)+(sum[n][1]>0)+(sum[n][2]>0)); 23 return ; 24 } 25 int nxt,k1,k2,k3,tmp,inf; 26 memset(f,127/3,sizeof(f));inf=f[0][0][0][0]; 27 f[10][sum[10][0]][sum[10][1]][sum[10][2]]=0; 28 for(int i=10;i<n;i++){ 29 for(int j=0;j<=10;j++) 30 for(int k=0;k<=10;k++) 31 for(int g=0;g<=10;g++){ 32 tmp=f[i][j][k][g]; 33 if(tmp==inf)continue; 34 if(j){ 35 nxt=min(i+j,n);k1=sum[nxt][0]-sum[i][0]; 36 k2=k+sum[nxt][1]-sum[i][1];k3=g+sum[nxt][2]-sum[i][2]; 37 if(tmp+1<f[nxt][k1][k2][k3]) 38 f[nxt][k1][k2][k3]=tmp+1; 39 } 40 if(k){ 41 nxt=min(i+k,n);k1=j+sum[nxt][0]-sum[i][0]; 42 k2=sum[nxt][1]-sum[i][1];k3=g+sum[nxt][2]-sum[i][2]; 43 if(tmp+1<f[nxt][k1][k2][k3]) 44 f[nxt][k1][k2][k3]=tmp+1; 45 } 46 if(g){ 47 nxt=min(i+g,n);k1=j+sum[nxt][0]-sum[i][0]; 48 k2=k+sum[nxt][1]-sum[i][1];k3=sum[nxt][2]-sum[i][2]; 49 if(tmp+1<f[nxt][k1][k2][k3]) 50 f[nxt][k1][k2][k3]=tmp+1; 51 } 52 } 53 } 54 int ans=inf; 55 for(int i=0;i<=10;i++){ 56 for(int j=0;j<=10;j++) 57 for(int k=0;k<=10;k++){ 58 tmp=f[n][i][j][k]+(i!=0)+(j!=0)+(k!=0); 59 if(tmp<ans)ans=tmp; 60 } 61 } 62 printf("%d ",ans); 63 } 64 int main() 65 { 66 work(); 67 return 0; 68 }