Written with .
Description
\(118\)号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有\(3\)种不同的纯度，\(A：100\%，B：1\%，C：0.01\%\)，为了出售方便，必须把不同纯度的成品分开装箱，装箱员\(grant\)第\(1\)次顺序从流水线上取\(10\)个成品（如果一共不足\(10\)个，则全部取出），以后每一次把手中某种纯度的成品放进相应的箱子，然后再从流水线上顺序取一些成品，使手中保持\(10\)个成品（如果把剩下的全部取出不足\(10\)个，则全部取出），如果所有的成品都装进了箱子，那么\(grant\)的任务就完成了。
由于装箱是件非常累的事情，\(grant\)希望他能够以最少的装箱次数来完成他的任务，现在他请你编个程序帮助他。Input
第\(1\)行为\(n（1<=n<=100）\)，为成品的数量.
以后\(n\)行，每行为一个大写字母\(A，B\)或\(C\)，表示成品的纯度。Ouput
仅一行，为\(grant\)需要的最少的装箱次数.
Sample Input
11
A B C A B C A B C A BSample Output
3
Solution
- 显然是一道记忆化搜索.
这道题的价值在于,可以传一个数组作为函数变量,减少代码量.
我又水了一篇
#include#define inf 0x3f3f3f3fusing namespace std;typedef long long LoveLive;inline int read(){ int out=0,fh=1; char jp=getchar(); while ((jp>'9'||jp<'0')&&jp!='-') jp=getchar(); if (jp=='-') { fh=-1; jp=getchar(); } while (jp>='0'&&jp<='9') { out=out*10+jp-'0'; jp=getchar(); } return out*fh;}const int MAXN=150;const int MAXT=30;int f[MAXN][MAXT][MAXT][MAXT];int n;int x[MAXN];int dfs(int k,int* g){ if(f[k][g[1]][g[2]][g[3]]!=-1) return f[k][g[1]][g[2]][g[3]]; if(g[1]+g[2]+g[3]==0) return 0; int &res=f[k][g[1]][g[2]][g[3]]; res=inf; int j; for(int i=1;i<=3;++i) { if(g[i]>0) { int t=g[i],t1=g[1],t2=g[2],t3=g[3]; g[i]=0; for(j=k;j<=n&&j<=(k+t-1);++j) ++g[x[j]]; res=min(res,dfs(j,g)+1); g[1]=t1,g[2]=t2,g[3]=t3; } } return res;}int main(){ memset(f,-1,sizeof f); n=read(); for(int i=1;i<=n;++i) { char c[2]; scanf("%s",c); x[i]=c[0]-'A'+1; } int i; int g[4]={0}; for(i=1;i<=n&&i<=10;i++) ++g[x[i]]; int ans=dfs(i,g); printf("%d\n",ans); return 0;}