模意义下最大子序列和（Easy Version）_

C++

jys1221

#include <iostream>

#include <vector>

using namespace std;

using ll = long long;

int n;

ll m, ans = 0;

vector<ll> a;

// dfs(i, sum) 表示当前在处理下标 i，已经累加的模值为 sum

void dfs(int i, ll sum) {

if (i == n) {

ans = max(ans, sum); // sum 本身就是 mod m 后的值

return;

}

// 不选 a[i]

dfs(i + 1, sum);

// 选 a[i]

dfs(i + 1, (sum + a[i] % m) % m);

}

int main() {

cin >> n >> m;

a.resize(n);

for (int i = 0; i < n; i++) {

cin >> a[i];

a[i] %= m;

}

dfs(0, 0);

cout << ans << "\n";

return 0;

}

发表于 2025-07-25 09:50:07 回复(0)

Java

清浅QAQ

import java.util.*;

public class Main {

static int res = 0;

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int m = in.nextInt();

int[] arr = new int[n];

for (int i = 0; i < n; i++) {

arr[i] = in.nextInt();

arr[i] %= m; // 预处理，减少后续计算量

}

track(arr, 0, n, m, 0);

System.out.println(res);

}

// public static void track(int[] arr, int index, int n, int m, int sum) {

// if (index == n) {

// res = Math.max(res, sum);

// return;

// }

// // 选择当前元素

// track(arr, index + 1, n, m, (sum + arr[index]) % m);

// // 不选择当前元素

// track(arr, index + 1, n, m, sum);

// }

public static void track(int[] arr, int index, int n, int m, int sum) {

// 每次递归都尝试更新最大值

res = Math.max(res, sum);

// 从当前index开始，尝试所有可能的子序列

for (int i = index; i < n; i++) {

// 选择arr[i]，并递归处理后面的元素

track(arr, i + 1, n, m, (sum + arr[i]) % m);

}

发表于 2025-09-22 21:42:00 回复(0)

草海桐

package main

import (
	"fmt"
)

func main() {
	var n, m int
	fmt.Scanf("%d %d", &n, &m)
	k := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &k[i])
	}

	result := 0

	var dfs func(i, sum int)
	dfs = func(i, sum int) {
		if i == n {
			modSum := sum % m
			if modSum > result {
				result = modSum
			}
			return
		}
		// 不选择当前元素
		dfs(i+1, sum)
		// 选择当前元素
		dfs(i+1, sum+k[i])
	}

	dfs(0, 0)
	fmt.Println(result)
}

发表于 2025-09-07 22:40:57 回复(0)

Python3

牛客847294653号

# 更新答案（考虑当前子序列）

n, m = map(int, input().strip().split())

a = list(map(int, input().strip().split()))

ans = 0

def dfs(i, current_sum):

global ans

# 更新答案（考虑当前子序列）

ans = max(ans, current_sum % m)

# 递归边界

if i == n:

return

# 选择当前元素

dfs(i + 1, (current_sum + a[i]) % m)

# 不选择当前元素

dfs(i + 1, current_sum)

# 从第一个元素开始，初始和为0

dfs(0, 0)

print(ans)

发表于 2025-08-23 13:19:34 回复(0)

模意义下最大子序列和（Easy Version）

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题