#C240929C. 贪心
标签(Label)
- 动态规划
- 贪心
- 背包问题(二进制优化多重背包dp)
- 二进制
网址(Website)
P8392 [BalticOI 2022 Day1] Uplifting Excursion - 洛谷
题目(Problem)
题目描述
有 $2m+1$ 种物品,重量分别为 $-m, -m+1, \ldots, m-1, m$。重量为 $i$ 的物品有 $a_i$ 个。
你需要拿走若干物品,使得这些物品重量之和恰好为 $L$。在此基础上,你需要拿尽可能多的物品。
问在物品重量之和恰好为 $L$ 的基础上,你最多能拿多少物品。
输入格式
第一行两个数 $m, L$。
第二行 $2m+1$ 个数,分别为 $a_{-m}, a_{-m+1}, \ldots, a_{m-1}, a_m$。
输出格式
一行一个数表示答案。若不存在方案,输出 impossible
样例1
输入复制
2 5
2 3 1 1 4
输出复制
9
一种方案数是分别取 $[1, 2, 1, 1, 4]$ 个,重量之和为 $5$。总共取了 $9$ 个物品。
样例2
输入复制
3 5
3 1 0 2 0 0 2
输出复制
impossible
可以证明不存在方案使得重量之和为 $5$。
样例3
输入复制
1 5
0 0 6
输出复制
5
数据范围与提示
- 子任务 1 (5 分):$M, a_i \leq 50$
- 子任务 2 (15 分):$M, a_i \leq 100$。
- 子任务 3 (20 分):$M \leq 30$。
- 子任务 4 (20 分):$M \leq 50$。
- 子任务 5 (20 分):$M \leq 100$。
- 子任务 6 (20 分):没有特殊限制。
对于子任务 3 到子任务 6,如果通过 $\forall i < 0, a_i = 0$ 的测试点,可以获得一半的得分。
对于所有数据,满足 $1 \leq M \leq 300, -10^{18} \le L \le 10^{18}, 0 \le a_i \le 10^{12}$。
题解(Solution)
$\qquad$令选择的正数物品加起来为 $lmx$ ,负数为 $lmn$ ,如果 $L\not \in [lmn,lmx]$ ,那么直接输出 $impossible$ 。将物品总和加起来 ,先从绝对值最大的数判断能否加减数,可以将 $L$ 调到 $[L-m,L+m]$ 范围。
$\qquad$发现这道题 $m\le 300$ ,考虑 $dp$ ,每个数有选择限制,有对应总量和价值,我们要求的就是重量和刚好为 $L$ 的时候选的尽量多的数的个数,考虑用多重背包优化dp。
$\qquad$由于每个数的限制 $a[i]$ 可能会很大,我们发现当这个数为 $1$ 的时候,最多选择 $2\times m$ 个,否则就会超出 $[L-m,L+m]$ 范围,而最大的数为 $m$ ,因此直接开 $2m^2$ 值域跑多重背包,时间复杂度 $O(m^5)$ ,用二进制优化后可以优化为 $O(m^3logm^2)$ 。
出题者题解
$\qquad$不妨设 $L \leq \sum_{|i| \leq n} i \cdot a_i$,首先有一个贪心策略是按重量从小到大选择物品,直到再选择就会超过 $L$,此时 $L_{now} \in (L - m, L]$。
$\qquad$考虑如何调整到最优解,每次调整只会让 $L_{now}$ 改变 $[-m, m]$,从而存在某种策略使得始终都有 $L_{now} \in (L - m, L + m]$。
$\qquad$ 并且,若某个 $L_{now}$ 重复出现,设期间加入和删除的数分别为 $A, B$,则有 $\text{sum}(A) = \text{sum}(B)$。由前述贪心策略知 $|A| < |B|$,这与最优性矛盾。
$\qquad$ 所以,背包的值域只需开到 $2m^2$,直接跑多重背包即可。可以使用二进制优化做到 $O(m^3 \log m)$ 或单调队列做到 $O(m^3)$。
代码(Code)
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 1005;
int *a,*b,n,L,siz;
int A[N],B[N];
int f[N*N];//f[i]对应 n*n+i
inline void add(int w,int v,int c){
if(w>0){
for(int s = 1;c>0;c -= s, s<<=1){
int k = min(s, c);
Rof(i,siz,w*k)
f[i] = max(f[i], f[i-w*k] + v*k);
}
}else{
for(int s = 1;c>0;c -= s, s<<=1){
int k = min(s, c);
For(i,0,siz+w*k)
f[i] = max(f[i], f[i-w*k] + v*k);
}
}
}
signed main(){
freopen("greedy.in", "r", stdin);
freopen("greedy.out", "w", stdout);
cin>>n>>L;int Tim = clock();
a = A+n, b = B+n;
For(i,-n,n) a[i] = b[i] = rd();
int lmn=0,lmx=0;
For(i,-n,n){
if(i<0) lmn += i*a[i];
if(i>0) lmx += i*a[i];
}if(L<lmn || lmx<L) printf("impossible\n"),exit(0);
int tot = lmn + lmx;//总个数
if(tot > L){//此时应该减正数
Rof(i,n,1){
int can = min(a[i], (tot-L)/i);
b[i] -= can;
tot -= i*can;
}
}else{//这个时候应该减负数
For(i,-n,-1){
int can = min(a[i], (tot-L)/i);
b[i] -= can;
tot -= i*can;
}
}
siz = 2*n*n;
memset(f,-0x3f,sizeof f);
f[n*n+tot-L] = 0;
For(i,-n,n) f[n*n+tot-L] += b[i];
For(i,-n,n){
if(b[i]>0) add(-i,-1,min(siz, b[i]));
if(a[i]-b[i]>0) add(i,1,min(siz, a[i]-b[i]));
}
if(f[n*n]<0) printf("impossible\n");
else printf("%lld\n",f[n*n]);
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}