UVA - 10163 Storage Keepers（二分答案+01背包）

题目链接

---

首先感谢洛谷大佬rayluo的详细题解，万分感激%%%

整个问题分为二分和DP两部分

二分

看到最小的最大、最大的最小这类字眼就需要考虑二分答案。假设我们二分出来的值为$x$。为了使$x$可行，也就是说每一个仓库的安全值都要大于等于$x$。而我们注意到，在这个式子中$p_i$为定值，$k$越大，式子的值越小，那么在$\frac{p_i}{k}\ge x$ 的情况下，$k$是有最大值的，为$\frac{p_i}{x}$，我们只需要使得每一个守卫的$k$的最大值之和大于等于$n$，那么这个$x$就是一个可行解，即：

bool check(int x){ if(x==0) return true; int cnt=0; for(int i=1;i<=m;i++){ cnt+=(p[i]/x); if(cnt>=n) return true; } return false; }

DP

我们将每个守卫看做物品，其雇佣金为价值。背包的容量为仓库的个数，那么每个人选或不选构成一个01背包的问题，但是因为每个人可能看守多个仓库，因此还需要增加一维。于是$d[i][j]$代表考虑到第$i$个守卫，前$i-1$个守卫已经考虑过，一共守卫的仓库个数为$j$。此外还要枚举$k$，$k$是第$i$个守卫保护的仓库数量。$x$是最小的最大安全系数，那么有：

$d[i][j]=min(d[i][j],d[i-1][j-k]+p[i]),p[i]/k\ge x$

初始为$d[0][0]=0$；最后的答案是$d[i][n],1\le i\le m$

易错点

另外一开始我写的是：

d[0][0]=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){ d[i][j]=d[i-1][j]; for(int k=1;k<=j;k++) if(p[i]/k>=x) d[i][j]=min(d[i][j],d[i-1][j-k]+p[i]); }

这样之所以会WA，因为我们的边界状态为$d[0][0]$，但是$d[1][1]$这个状态初始化为$d[1][1]=d[0][1]$，显然是不对的，因此$j$要从0开始枚举。当然如果滚动数组优化后就没有这个忧患了

朴素01背包代码

#include <set> #include <map> #include <stack> #include <queue> #include <math.h> #include <cstdio> #include <string> #include <bitset> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define lowbit(x) (x&(-x)) #define mkp(x,y) make_pair(x,y) #define mem(a,x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> P; const double eps=1e-8; const double pi=acos(-1.0); const int inf=0x3f3f3f3f; const ll INF=1e18; const int Mod=1e9+7; const int maxn=2e5+10; int n,m; int p[maxn],d[35][105]; bool check(int x){ if(x==0) return true; int cnt=0; for(int i=1;i<=m;i++){ cnt+=(p[i]/x); if(cnt>=n)return true; } return false; } int dp(int x){ if(x==0) return 0; memset(d,inf,sizeof d); d[0][0]=0; for(int i=1;i<=m;i++) for(int j=0;j<=n;j++){ d[i][j]=d[i-1][j]; for(int k=1;k<=j;k++) if(p[i]/k>=x) d[i][j]=min(d[i][j],d[i-1][j-k]+p[i]); } int ans=inf; for(int i=1;i<=m;i++) ans=min(ans,d[i][n]); return ans; } int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); while(cin>>n>>m && n){ int l=0,r=0,ans=0; for(int i=1;i<=m;i++){ cin>>p[i]; r=max(r,p[i]); } while(l<=r){ int mid=(l+r)/2; if(check(mid)){ l=mid+1; ans=mid; }else r=mid-1; } cout<<ans<<" "<<dp(ans)<<endl; } return 0; }

滚动数组优化代码

#include <set> #include <map> #include <stack> #include <queue> #include <math.h> #include <cstdio> #include <string> #include <bitset> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define lowbit(x) (x&(-x)) #define mkp(x,y) make_pair(x,y) #define mem(a,x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> P; const double eps=1e-8; const double pi=acos(-1.0); const int inf=0x3f3f3f3f; const ll INF=1e18; const int Mod=1e9+7; const int maxn=2e5+10; int n,m; int p[maxn],d[105]; bool check(int x){ if(x==0) return true; int cnt=0; for(int i=1;i<=m;i++){ cnt+=(p[i]/x); if(cnt>=n)return true; } return false; } int dp(int x){ if(x==0) return 0; memset(d,inf,sizeof d); d[0]=0; for(int i=1;i<=m;i++) for(int j=n;j>=1;j--){ for(int k=1;k<=j;k++) if(p[i]/k>=x) d[j]=min(d[j],d[j-k]+p[i]); } return d[n]; } int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); while(cin>>n>>m && n){ int l=0,r=0,ans=0; for(int i=1;i<=m;i++){ cin>>p[i]; r=max(r,p[i]); } while(l<=r){ int mid=(l+r)/2; if(check(mid)){ l=mid+1; ans=mid; }else r=mid-1; } cout<<ans<<" "<<dp(ans)<<endl; } return 0; }