题目

区间 \(01\) 背包

\(1 \le l_i \le r_i \le n \le 20000,1 \le q \le 100000,1 \le m_i \le 500, 1 \le w_i \le 500, 1 \le v_i \le 10^6\)

分析

显然，我们考虑区间背包的合并

于是可以考虑分治策略

我们每次处理跨区间的询问

那么可以以 \(mid\) 为起点，往左做一遍后缀背包（不一定装满），往右做一遍前缀背包（一定装满）

一个在本区间且跨 \(mid\) 的询问就可以用这些拼起来，统计答案即可

不在本区间的分治处理即可

上面限制了背包装不装满是为了不重复的统计

于是时间复杂度就是 \(O(nm\log n + qm)\)

\(Code\)

#include<cstdio>

#include<vector>

#define ls (k << 1)

#define rs (ls | 1)

using namespace std;

const int N = 2e4 + 5, M = 505, Q = 1e5 + 5;

const int INF = 0x3f3f3f3f, P = 998244353;

int n, q, Mx, v[N], w[N], f[N][M], g[N][M];

struct node{int l, r, m;}a[Q];

struct answer{int val, g;}ans[Q];

vector<int> st[Q << 2];

void solve(int k, int L, int R)

{

	if (!st[k].size()) return;

	int mid = (L + R) >> 1;

	f[mid][0] = 0, g[mid][0] = 1;

	for(register int i = mid; i <= R; i++)

	{

		g[i][0] = 1;

		for(register int j = 1; j <= Mx; j++) f[i][j] = -INF, g[i][j] = 0;

	}

	for(register int i = mid + 1; i <= R; i++)

	{

		for(register int j = 0; j <= Mx; j++) f[i][j] = f[i - 1][j], g[i][j] = g[i - 1][j];

		for(register int j = w[i]; j <= Mx; j++)

		{

			int val = f[i - 1][j - w[i]] + v[i];

			if (val > f[i][j]) f[i][j] = val, g[i][j] = g[i - 1][j - w[i]];

			else if (val == f[i][j]) g[i][j] = (g[i][j] + g[i - 1][j - w[i]]) % P;

		}

	}

	for(register int i = mid; i >= L; i--)

		for(register int j = 0; j <= Mx; j++) f[i][j] = 0, g[i][j] = 1;

	for(register int i = w[mid]; i <= Mx; i++) f[mid][i] = v[mid], g[mid][i] = 1;

	for(register int i = mid - 1; i >= L; i--)

	{

		for(register int j = 0; j <= Mx; j++) f[i][j] = f[i + 1][j], g[i][j] = g[i + 1][j];

		for(register int j = w[i]; j <= Mx; j++)

		{

			int val = f[i + 1][j - w[i]] + v[i];

			if (val > f[i][j]) f[i][j] = val, g[i][j] = g[i + 1][j - w[i]];

			else if (val == f[i][j]) g[i][j] = (g[i][j] + g[i + 1][j - w[i]]) % P;

		}

	}

	for(register int i = 0; i < st[k].size(); i++)

	{

		int now = st[k][i], l = a[now].l, r = a[now].r, m = a[now].m;

		if (l == mid && r == mid) ans[now].val = ((m >= w[mid]) ? (v[mid]) : 0), ans[now].g = 1;

		else if (l > mid) st[rs].push_back(now);

		else if (r <= mid) st[ls].push_back(now);

		else{

			for(register int j = 0; j <= m; j++)

			{

				int val = f[r][j] + f[l][m - j];

				if (val > ans[now].val) ans[now].val = val, ans[now].g = (long long)g[r][j] * g[l][m - j] % P;

				else if (val == ans[now].val) ans[now].g = (ans[now].g + (long long)g[r][j] * g[l][m - j]) % P;

			}

		}

	}

	if (L == R) return;

	solve(ls, L, mid), solve(rs, mid + 1, R);

}

int main()

{

	freopen("knapsack.in", "r", stdin);

	freopen("knapsack.out", "w", stdout);

	scanf("%d", &n);

	for(register int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);

	scanf("%d", &q);

	for(register int i = 1; i <= q; i++)

		scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].m), Mx = max(Mx, a[i].m), st[1].push_back(i);

	solve(1, 1, n);

	for(register int i = 1; i <= q; i++)

	{

		if (ans[i].val == 0) printf("0 0\n");

		else printf("%d %d\n", ans[i].val, ans[i].g);

	}

}

巴特西

noip2020模拟赛背包 (knapsack)

题目

分析

\(Code\)

最新文章

热门文章

巴特西

noip2020模拟赛 背包 (knapsack)

题目

分析

\(Code\)

最新文章

热门文章

noip2020模拟赛背包 (knapsack)