Written with StackEdit.
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
B
Sample Output
3
Solution
- 显然是一道记忆化搜索.
-
这道题的价值在于,可以传一个数组作为函数变量,减少代码量.
我又水了一篇
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using 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;
}