P2530 [SHOI2001] 化工厂装箱员 题解

450 字
2 分钟
P2530 [SHOI2001] 化工厂装箱员 题解

首先我第一眼看到这道题时以为这是一道贪心,贪心策略是对于每一次手里的 1010 个货物都优先放下个数最多的。当然这后来想一想便是错误的,因为如果假如手里有 66 个 AA,但是手里有 44 个 BB,而且 66 个是一个 AA,55 个 CC,那么这个贪心策略很明显就不满足最优解了。

所以考虑 dpdp,一开始我是想开四维数组,一维用来记录 dpdp 到第几个了,另外三维用来记录所有没拿出去的 A,B,CA,B,C 的个数,但是后来发现这样需要维护的东西太多,那么经过观察范围发现我的数组设计应该是没有问题的,那么就改变一下状态设计,对于转移来说,最优秀的便是把后面三个维度转换成现在手里所持有的三个物品的个数,这样数组提供的信息就足够维持我们的 dpdp 转移了,如何转移写在代码注释里了。

复杂度:O(1000n)=O(n2n)\mathrm{O}(1000n)=O(n^2\sqrt[]{n})

code:#

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,a[N],dp[N][11][11][11];
string s;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){//使用字符串防止玄学出锅
cin>>s;
a[i]=s[0]-'A'+1;
}
memset(dp,0x3f,sizeof dp);//因为要取最小值所以dp数组初始化极大值
dp[0][0][0][0]=0;//dp起点设置
for(int T=1;T<=n;T++){
for(int i=0;i<=10;i++){
for(int j=0;j<=10;j++){
for(int k=0;k<=10;k++){
if(i+j+k>10) continue;//如果三个相加超过10的话这个状态不合法
if(a[T]==1&&i!=0){//以下三个if分别表示对于a[T]的每一种情况只拿进来却不放下
dp[T][i][j][k]=min(dp[T][i][j][k],dp[T-1][i-1][j][k]);
}
if(a[T]==2&&j!=0){
dp[T][i][j][k]=min(dp[T][i][j][k],dp[T-1][i][j-1][k]);
}
if(a[T]==3&&k!=0){
dp[T][i][j][k]=min(dp[T][i][j][k],dp[T-1][i][j][k-1]);
}
dp[T][0][j][k]=min(dp[T][0][j][k],dp[T][i][j][k]+1);//以下三行对应的是这一次拿出每一种的可能
dp[T][i][0][k]=min(dp[T][i][0][k],dp[T][i][j][k]+1);
dp[T][i][j][0]=min(dp[T][i][j][0],dp[T][i][j][k]+1);
}
}
}
}
printf("%d",dp[n][0][0][0]);//因为最后手里什么都不剩,所以输出全为0的状态
return 0;
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

P2530 [SHOI2001] 化工厂装箱员 题解
https://rechenz.github.io/post/p2530/
作者
热尘
发布于
2023-06-29
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
热尘
游戏开发者 · AI 爱好者
公告
欢迎来到我的博客!这是一则示例公告。
分类
标签
站点统计
文章
38
分类
5
标签
12
总字数
46,029
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录