【背包】ZJCPC M

╰+攻爆jí腚メ 2024-03-23 14:55 48阅读 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;
    }