CF1433F Zero Remainder Sum

写在前面

思维难度不是很大的 DP，代码实现也很容易。

状态设计模式很套路，转移也很好理解。

算法思路

（因为 \(k\) 是常用的循环变量，下文中将题面中的模数改为 \(p\)）

虽然要求的是模 \(p\) 结果为 \(0\) 的答案，显然这个结果受到选择的数的和可能受到模 \(p\) 任何余数的影响。因此不妨设计状态的时候想到用一维来表示答案模 \(p\) 的余数。

加上这一维之后就是一个背包模板了。

设 \(f_{i, j, t, k}\) 表示在第 \(i\) 行前 \(j\) 个数中选出 \(t\) 个数，且模 \(p\) 余 \(k\) 的最大答案。

那么显然有:

\[f_{i, j, t, k} = \max\{f_{i, j - 1, t, k}, f_{i, j - 1, t - 1, (k - a_{i, j})\bmod p} + a_{i, j}\}
\]

当可能存在多个（或多组） \(a_{i, j}\) 可能将同一个答案更新的时候，取最大值即可。

这样分别处理处每一行的答案之后，再设 \(g_{i, j}\) 表示在前 \(i\) 行中选择某些数使得其和模 \(p\) 的余数为 \(j\) 的最大答案。

那么显然有:

\[g_{i, j} = \max\{g_{i - 1, (j - k)\bmod p} + f_{i, m, t, k}\}
\]

Tips

注意一些边界条件。
处理的时候可能会出现不合法的状态，即在某一行内选出某些数，其和模 \(p\) 的余数根本不可能等于枚举的 \(k\) 的情况。这种处理方式归根到底还是因为它是从“选 \(0\) 个数的时候余数却不为 \(0\)”这个不合法状态转移来的。有个简单的处理方式，只需要将初值设为负无穷，然后将合法的初始状态（即选择数的个数和余数都为 \(0\)）设为 \(0\) 就好了。

Code

代码中对于每一行分别处理了这一行的 \(f\) 数组，并紧接着更新 \(g\) 数组，因此将 \(f\) 数组删掉了一维。
代码中还使用了滚动数组。

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 75;

namespace Read {

	inline int read() {

		int fh = 1, res = 0; char ch = getchar();

		for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;

		for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');

		return fh * res;

	}

}

using namespace Read;

int n, m, p;

int a[Maxn][Maxn];

int f[2][Maxn][Maxn];

int g[2][Maxn];

int main() {

	n = read(); m = read(); p = read();

	for(register int i = 1; i <= n; ++i) {

		for(register int j = 1; j <= m; ++j) {

			a[i][j] = read();

		}

	}

	memset(g, -0x3f, sizeof(g));

	g[0][0] = 0;

	for(register int i = 1; i <= n; ++i) {

		memset(f, -0x3f, sizeof(f));

		f[0][0][0] = 0;

		for(register int j = 1; j <= m; ++j) {

			f[j & 1][0][0] = 0;

			for(register int t = 1; t <= min(j, m/2); ++t) {

				for(register int k = 0; k < p; ++k) {

					f[j & 1][t][k] = max(max(f[j & 1][t][k], f[j - 1 & 1][t][k]), f[j - 1 & 1][t - 1][(k - (a[i][j] % p) + p) % p] + a[i][j]);

				}

			}

		}

		for(register int j = 0; j < p; ++j) {

			g[i & 1][j] = g[i - 1 & 1][j];

			for(register int t = 0; t <= (m / 2); ++t) {

				for(register int k = 0; k < p; ++k) {

					g[i & 1][j] = max(g[i & 1][j], g[i - 1 & 1][(j - (f[m & 1][t][k] % p) + p) % p] + f[m & 1][t][k]);

				}

			}

		}

	}

	printf("%d", g[n & 1][0]);

	return 0;

}

巴特西

CF1433F Zero Remainder Sum

写在前面

算法思路

Tips

Code

最新文章

热门文章