P2530 [SHOI2001] 化工厂装箱员 题解
450 字
2 分钟
P2530 [SHOI2001] 化工厂装箱员 题解
首先我第一眼看到这道题时以为这是一道贪心,贪心策略是对于每一次手里的 个货物都优先放下个数最多的。当然这后来想一想便是错误的,因为如果假如手里有 个 ,但是手里有 个 ,而且 个是一个 , 个 ,那么这个贪心策略很明显就不满足最优解了。
所以考虑 ,一开始我是想开四维数组,一维用来记录 到第几个了,另外三维用来记录所有没拿出去的 的个数,但是后来发现这样需要维护的东西太多,那么经过观察范围发现我的数组设计应该是没有问题的,那么就改变一下状态设计,对于转移来说,最优秀的便是把后面三个维度转换成现在手里所持有的三个物品的个数,这样数组提供的信息就足够维持我们的 转移了,如何转移写在代码注释里了。
复杂度:
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;}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!
相关文章智能推荐
1
P5032 经验 题解
算法竞赛2023-09-25
2
P4209 学习小组 题解
算法竞赛2023-06-17
3
SP688 SAM - Toy Cars题解
算法竞赛2023-06-12
4
P6413 [COCI2008-2009#3] NAJKRACI 题解
算法竞赛2023-10-31
5
P9705 「TFOI R1」Unknown Graph 题解
算法竞赛2023-10-16
随机文章随机推荐

