没有用二进制或单调队列优化,开O2直接AC?
查看原帖
没有用二进制或单调队列优化,开O2直接AC?
804607
rainygame楼主2023/1/9 10:36

RT。稍微用了一下我的原创卡常多重背包优化,妹想到直接AC。

加强一下数据吧……

#include <bits/stdc++.h>
using namespace std;
#define MAXN 101

long long n, v;
long long m[MAXN], w[MAXN], s[MAXN], f[40004];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> v;
	for (int i=1; i<=n; i++) cin >> s[i] >> w[i] >> m[i];

	for (int i=1; i<=n; i++){
		for (int j=v; j>=0; j--){
			for(int k=0; k<=min(m[i], j/w[i]); k++) f[j]=max(f[j], f[j-k*w[i]]+k*s[i]);
		}
	}

	cout << f[v];

	return 0;
}

(注:原多重背包模板的第三层循环中 kk 的终止条件为 min{mi,Wwi}\min \{m_i,\frac{W}{w_i} \},现在改成了 min{mi,jwi}\min \{m_i,\frac{j}{w_i} \},也删除了一个判断)

最后再希望能加强一下数据,最好是能卡过这个代码的O2的数据。(最后一个点永远 907ms907ms,应该很好改)

2023/1/9 10:36
加载中...