关键词：
题目描述
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需要的最少的装箱次数。
输入输出样例
11
A
B
C
A
B
C
A
B
C
A
B
3
题解：
dp[i][a][b][c]为取了i次，A剩a个，B剩b个，C剩c个。
代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int z[120],dp[120][12][12][12]; int n,inf; int dfs(int p,int a,int b,int c){ if(p==n){ dp[n][a][b][c]=(a>0)+(b>0)+(c>0); return dp[p][a][b][c]; } for(;a+b+c<10;){ p++; if(z[p]==1)a++; if(z[p]==2)b++; if(z[p]==3)c++; if(p==n)break; } if(dp[p][a][b][c]!=inf)return dp[p][a][b][c]; if(a)dp[p][a][b][c]=min(dp[p][a][b][c],dfs(p,0,b,c)+1); if(b)dp[p][a][b][c]=min(dp[p][a][b][c],dfs(p,a,0,c)+1); if(c)dp[p][a][b][c]=min(dp[p][a][b][c],dfs(p,a,b,0)+1); return dp[p][a][b][c]; } int main(){ scanf("%d",&n);char ch; inf=0x3f3f3f3f; memset(dp,0x3f,sizeof(dp)); for(int i=1;i<=n;i++){ ch=getchar(); while(ch<‘A‘||ch>‘C‘)ch=getchar(); int x=ch-‘A‘+1; z[i]=x; } printf("%d",dfs(0,0,0,0)); return 0; }
p2530[shoi2001]化工厂装箱员(代码片段)
题目描述118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱... 查看详情
题解shoi2001化工厂装箱员
————传送：洛谷P2530这道题目还是挺简单的，状态也容易想到。数据范围非常的小，所以即便是很多维度，复杂度也完全可以接受。定义状态：dp[i][a][b][c]为手上的货物拿到第i个时三种物品分别有a,b,c个所用的最少次数。状... 查看详情
洛谷p2530化工场装箱员
...uogu.org/problem/show?pid=2530118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分... 查看详情
洛谷p2527[shoi2001]panda的烦恼
题目描述panda是个数学怪人，他非常喜欢研究跟别人相反的事情。最近他正在研究筛法，众所周知，对一个范围内的整数，经过筛法处理以后，剩下的全部都是质数，不过panda对这些不感兴趣，他只对被筛掉的数感兴趣，他... 查看详情
洛谷3833shoi2012魔法树
【题解】 树链剖分模板题。。#include<cstdio>#include<algorithm>#include<queue>#defineN500010#definergregister#definels(u<<1)#definers(u<<1|1)#definemid((a[u].l+a[u].r)>>1)#defin 查看详情
洛谷1165日志分析
题目描述M海运公司最近要对旗下仓库的货物进出情况进行统计。目前他们所拥有的唯一记录就是一个记录集装箱进出情况的日志。该日志记录了两类操作：第一类操作为集装箱入库操作，以及该次入库的集装箱重量；第二类操... 查看详情
排序工作量之新任务（shoi2001）
排序工作量之新任务（SHOI2001）给出两个整数n和t，求n的全排列中逆序对数为t的个数，和逆序对数为t的字典序最小全排列。首先第一个问题可以用dp解决，\(f[i][j]\)表示前i个数，j个逆序对的序列数，那么\(f[i][j]=f[i-1][j-k]\(k<i)(k... 查看详情
luogup2526_[shoi2001]小狗散步_二分图匹配
luoguP2526_[SHOI2001]小狗散步_二分图匹配题意：Grant喜欢带着他的小狗Pandog散步。Grant以一定的速度沿着固定路线走，该路线可能自交。Pandog喜欢游览沿途的景点，不过会在给定的N个点和主人相遇。小狗和主人同时从(X1，Y1)点出发，... 查看详情
[luogup2526][shoi2001]小狗散步（二分图最大匹配）
传送门 简直就是模板题啊！ #include<cmath>#include<cstdio>#include<cstring>#include<iostream>#defineN101usingnamespacestd;intn,m,cnt;intX1[N],Y1[N],X2[N],Y2[N],head[N],to[N*N],nex 查看详情
2001装箱问题
题目描述 Description有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入描述 InputDescripti... 查看详情
noip2001装箱问题（codevs1014）
装箱问题题目描述 Description 有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有 查看详情
bzoj2830&洛谷3830：[shoi2012]随机树——题解(代码片段)
https://www.luogu.org/problemnew/show/P3830#sub <-题面看这里~https://www.lydsy.com/JudgeOnline/problem.php?id=2830感觉智商被压制了的一题……后面放吐槽。参考：https://www.cnblogs.com/GuessYCB/p/846249 查看详情
●洛谷p1291[shoi2002]百事世界杯之旅
题链：https://www.luogu.org/recordnew/show/5861351题解：dp，期望 定义dp[i]表示还剩下i个盖子没收集时，期望还需要多少次才能手机完。 初始值：dp[0]=0 显然对于一个状态，我们随机得到一个盖子，有两种可能： 1.得到了曾经没有的盖子... 查看详情
洛谷p4332[shoi2014]三叉神经树题解(代码片段)
一、题目：洛谷原题二、思路：这道题怎么说呢？只能说有点意思，让我第一次见识了LCT怎么应用。首先一个非常明显的性质，就是比如我现在修改了某个叶子结点，记为\\(leaf\\)，那么因此而状态发生改变的点一定是从\\(leaf\\)... 查看详情
[p2526][shoi2001]小狗散步(代码片段)
Link:P2526传送门Solution:一道提示非常到位的题目题面中强调了在两个路径相邻点间只能再去至多一个点，且每个点只计算一次贡献于是明显可以将原题看作询问在两个不相交点集间最多能连几条边接下来将合法边连上跑二分图匹... 查看详情
洛谷3830[shoi2012]随机树概率dp(代码片段)
题目输入格式输入仅有一行，包含两个正整数q,n，分别表示问题编号以及叶结点的个数。输出格式输出仅有一行，包含一个实数d，四舍五入精确到小数点后6位。如果q=1，则d表示叶结点平均深度的数学期望值；如果q=2，则d表示... 查看详情
洛谷p1314聪明的质监员
P1314聪明的质监员题目描述小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到n逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是：1、给定m个区间[Li,Ri]；2、选出一个参数W；3... 查看详情
洛谷p3195[hnoi2008]玩具装箱toy
题目：https://www.luogu.org/problemnew/show/P3195题目描述P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授... 查看详情