veteran233QAQ的博客
0%

Codeforces Round 677 - F - Zero Remainder Sum

发表于 更新于

题目

https://codeforces.com/contest/1433/problem/F

思路

dp，设$dp(x,y,cnt,rem)$，$x,y,cnt,rem$分别代表行、列、选择的个数和$k$的余数。
对于$a_{x,y}$，有两种选择：选或不选。对应的转移方程为：

除了$dp(1,0,0,0)$初始化为0，其余$dp(x,y,cnt,rem)$初始为$-\infty$，答案为$\max\limits_{0\leq i\leq\lfloor\frac{m}{2}\rfloor}(dp(n,m,i,0))$

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); } }_io;
typedef long long ll; typedef long double db;

ll a[75][75], dp[75][75][75][75];

int main()
{
	ll n, m, k;
	cin >> n >> m >> k;

	for (ll i = 1; i <= n; ++i)
		for (ll j = 1; j <= m; ++j)
			cin >> a[i][j];

	for (ll i = 0; i < 75; ++i)
		for (ll j = 0; j < 75; ++j)
			for (ll x = 0; x < 75; ++x)
				for (ll y = 0; y < 75; ++y)
					dp[i][j][x][y] = -1e12;

	dp[1][0][0][0] = 0;

	for (ll x = 1; x <= n; ++x)
	{
		for (ll y = 1; y <= m; ++y)
			for (ll cnt = 0; cnt <= m / 2; ++cnt)
				for (ll rem = 0; rem < k; ++rem)
				{
					dp[x][y][cnt][rem] = max(dp[x][y][cnt][rem], dp[x][y - 1][cnt][rem]);

					if (cnt + 1 <= m / 2)
					{
						ll t = (rem + a[x][y]) % k;
						dp[x][y][cnt + 1][t] = max(dp[x][y][cnt + 1][t], dp[x][y - 1][cnt][rem] + a[x][y]);
					}
				}
		if (x < n)
		{
			for (ll cnt = 0; cnt <= m / 2; ++cnt)
				for (ll rem = 0; rem < k; ++rem)
					dp[x + 1][0][0][rem] = max(dp[x + 1][0][0][rem], dp[x][m][cnt][rem]);
		}
	}

	ll ans = 0;
	for (ll i = 0; i <= m / 2; ++i) ans = max(ans, dp[n][m][i][0]);

	cout << ans << endl;

	return 0;
}