牛客网 牛牛去买球 (思维题01背包)

题目

牛牛想去商店买一些球来玩，他发现商店里有n个盒子，每个盒子外面有一张标签告诉你有ai个红球，bi个蓝球，需要ci的钱购买

但是由于店主是一个粗心的人,他告诉你每个盒子球的总量是符合标签的说明的,但是具体的种类可能会有如下偏差,

比如可能有(ai+1 ,bi-1),(ai, bi), (ai-1, bi+1)三种可能

牛牛想要买至少K个同颜色的球,但是他又不想浪费钱

帮他算算最少花多少钱买盒子能够使得至少会有K个球是同色的

n<=50，1<=ai,bi,ci,K<=1e4

思路来源

https://blog.csdn.net/why932346109/article/details/101373088

题解

至少有K个球是同色，先分开考虑两种球，

考虑每次都是单色最坏情况

即每次都是ai-1，考虑ai；或每次都是bi-1，考虑bi，分别做两次01背包

再注意到二者和不变，那么当二者和>=2k-1时，最大球个数一定>=k

鸽巢原理，再对二者和01背包一次，三者取小

代码

#include <bits/stdc++.h> using namespace std; const int N=1e4+10; const int INF=0x3f3f3f3f; const int K=2e4; int n,k,dp[K+10],ans; int a[55],b[55],c[55]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i) scanf("%d",&b[i]); for(int i=1;i<=n;++i) scanf("%d",&c[i]); ans=INF; memset(dp,INF,sizeof dp); dp[0]=0; for(int i=1;i<=n;++i) { for(int j=K;j>=a[i]-1;--j) { dp[j]=min(dp[j],dp[j-(a[i]-1)]+c[i]); } } for(int i=k;i<=K;++i) ans=min(ans,dp[i]); memset(dp,INF,sizeof dp); dp[0]=0; for(int i=1;i<=n;++i) { for(int j=K;j>=b[i]-1;--j) { dp[j]=min(dp[j],dp[j-(b[i]-1)]+c[i]); } } for(int i=k;i<=K;++i) ans=min(ans,dp[i]); memset(dp,INF,sizeof dp); dp[0]=0; for(int i=1;i<=n;++i) { for(int j=K;j>=a[i]+b[i];--j) { dp[j]=min(dp[j],dp[j-(a[i]+b[i])]+c[i]); } } for(int i=2*k-1;i<=K;++i)//保证和为i时 最多的那个>=k ans=min(ans,dp[i]); printf("%d\n",ans==INF?-1:ans); return 0; }