#C241001B. 简单背包

标签（Label）

背包
观察+分析

网址（Website）

题目详情 - 简单背包 - Super

题解 - 简单背包 - Super

题解（Solution）

$\qquad$分布理解题意即可。

出题者题解

算法分析

矿石价值单调不减，所以单位质量的矿石有用物质含量越多则价值越大。

记 $f_m$ 代表矿石（合并后）质量为 $m$ 时的最大价值，可以利用 $a_i, b_i$ 跑一个完全背包求出。

问题转化为至多 $m$ 种质量各不相同，价值已经确定的矿石放入容量为 $m$ 的背包时的最大价值，同样可以用一个完全背包求出。

时间复杂度 $O(nm + m^2)$

代码（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 = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;

int v[12],n,m;
int a[N],b[N];

int f1[N],f2[N];

inline int get(int a,int b){
	if(b==-inf) return 0;
	For(i,1,10) if(10*b<=a*i) return v[i];
	return 0;	
} 

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("bag.in","r",stdin);

	freopen("bag.out","w",stdout);
	For(i,1,10) v[i] = rd(); 
	n = rd(), m = rd();
	For(i,1,n) a[i] = rd(), b[i] = rd();
	int Tim = clock();
	
	For(i,1,m) f1[i] = -inf; 
	For(i,1,n) For(j,a[i],m)
		f1[j] = max(f1[j-a[i]] + b[i], f1[j]);
	
	For(i,1,m){
		int t = get(i,f1[i]) * i;
		For(j,i,m) f2[j] = max(f2[j], f2[j-i]+t);
	}
	cout<<f2[m]<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}