[vijos1323]-[SHOI2001]化工厂装箱员

发布于 2017-09-08  23 次阅读



题目(vijos)
这题一看就知道是个动态规划。
所以我们用记忆化搜索(喂)。
用dp[r][a][b][c]用来存前r个字符里,前10个字符中A有a个,B有b个,C有c个时,已经执行了多少次操作。
然后记忆化搜索。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n;
int dp[110][15][15][15];
char c[1];
int s[110];
int dfs(int r,int a,int b,int c)
{
	int p=10-a-b-c;
	for (int i=1;i<=p;++i)
	{
		r++;
		if (r>n) break;
		if (s[r]==1) ++a;
		if (s[r]==2) ++b;
		if (s[r]==3) ++c;
	}
	if (r>n)
		return dp[r][a][b][c]=(a>0)+(b>0)+(c>0);
	if (dp[r][a][b][c]) return dp[r][a][b][c];
	int sum=1e8;
	if (a>0) sum=min(sum,dfs(r,0,b,c)+1);
	if (b>0) sum=min(sum,dfs(r,a,0,c)+1);
	if (c>0) sum=min(sum,dfs(r,a,b,0)+1);
	return dp[r][a][b][c]=sum;
}
int main()
{
	scanf(
	for (int i=1;i<=n;++i)
	{
		scanf(
		s[i]=c[0]-'A'+1;
	}
	int ans=dfs(0,0,0,0);
	printf(
	return 0;
}