【背包】ZJCPC M

╰+攻爆jí腚メ 2024-03-23 14:55 54阅读 0赞

**现在还没交题的地方，不知道对不对，但是大概率是对的**

**这就是个s b背包，赛场上连样例都过不了，还是之后队友硬分类讨论过的**

**今天写了下一下就过样例了**

**和比赛的时候写的唯一不一样的就是答案统计，答案肯定是要枚举统计一下才行，而不是dp\[n\]\[x\]\[y\]，因为最终答案不止x和y**

**但是其实也没什么大不了的，就算赛场上一眼过了也拿不到铜，因为不会F....，比赛的时候队友开的F，我去看G去了，结果发现G是金牌题....全程没看榜**

**还没看过F，今晚去看看F，如果秒掉了，说明还是很可惜的....**

**Code：**

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=3e5+10;
    const int Inf=0x3f3f3f3f; 
    
    int n,x,y;
    int a[mxn],b[mxn];
    int dp[55][10][10];//考虑前i个，已经选了个x个cup和y个plate所需盘子数 
    void solve(){
    	memset(dp,0x3f,sizeof(dp));
    	cin>>n>>x>>y;
    	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    	dp[0][0][0]=0;
    	for(int i=1;i<=n;i++){
    		for(int j=0;j<=1;j++){
    			for(int k=0;k<=4;k++){
    				dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]);
    				if(j>=a[i]&&k>=b[i]) dp[i][j][k]=min(dp[i][j][k],dp[i-1][j-a[i]][k-b[i]]+1); 
    			}
    		}
    	}
    	
    	int ans=Inf;
    	for(int j=x;j<=1;j++){
    		for(int k=y;k<=4;k++){
    			ans=min(ans,dp[n][j][k]);
    		}
    	}
    	if(ans==Inf) cout<<"IMPOSSIBLE"<<'\n';
    	else cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，54人围观）

还没有评论，来说两句吧...

相关阅读

相关【背包】ZJCPC M

现在还没交题的地方，不知道对不对，但是大概率是对的这就是个s b背包，赛场上连样例都过不了，还是之后队友硬分类讨论过的今天写了下一下就过样例了和比赛的时候写的唯一不

╰+攻爆jí腚メ/ 2024年03月23日 14:55/ 0 赞/ 55 阅读

相关动态规划-背包问题(01背包、完全背包、多重背包)

背包问题 0/1背包原理输出方案例题HDU-2602 空间优化-滚动数组完全背包转

港控/mmm°/ 2023年02月28日 05:52/ 0 赞/ 37 阅读

相关背包问题详解：01背包、完全背包、多重背包

参考链接： 1. [http://www.cnblogs.com/fengty90/p/3768845.html][http_www.cnblogs.com_fengty9

蔚落/ 2022年09月30日 00:54/ 0 赞/ 275 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 282 阅读

相关背包问题(0-1背包、完全背包、多重背包)详解

背包问题一个背包总容量为V, 现在有N个物品, 第i个物品容量为weight\[i\], 价值为value\[i\], 现在往背包里面装东西, 怎样装才能使背包内物品总

柔情只为你懂/ 2022年06月08日 00:59/ 0 赞/ 373 阅读

相关算法——背包问题 01背包+完全背包+多重背包

01背包：https://biancheng.love/problem/51/index 有n 种不同的物品，每个物品有两个属性，weight重量，value 价值，现在给一

ゞ浴缸里的玫瑰/ 2022年06月06日 10:41/ 0 赞/ 340 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 398 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 328 阅读

相关 M - Dividing(完全背包+二进制优化)

题意： Marsha and Bill own a collection of marbles. They want to split the collection am

偏执的太偏执、/ 2022年04月23日 16:06/ 0 赞/ 212 阅读

相关 ZOJ 2972 Hurdles of 110m 【DP 背包】

一共有N段过程，每段过程里可以选择快速跑、匀速跑和慢速跑对于快速跑会消耗F1 的能量，慢速跑会集聚F2的能量选手一开始有M的能量，即能量上限求通过全程的最

Dear 丶/ 2021年12月10日 16:45/ 0 赞/ 255 阅读