#C240929C. 贪心


#C240929C. 贪心

标签(Label)

  • 动态规划
  • 贪心
  • 背包问题(二进制优化多重背包dp)
  • 二进制

网址(Website)

题目详情 - 贪心 - Super

题解 - 贪心 - Super

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;
}

文章作者: WolfDeer
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 WolfDeer !
  目录