每日OJ题_牛客_DP40小红取数_01背包+同余_C++_Java

目录

牛客_DP40小红取数_01背包+同余

题目解析

C++代码

Java代码

---

牛客_DP40小红取数_01背包+同余

小红取数_牛客题霸_牛客网

描述：

        小红拿到了一个数组，她想取一些数使得取的数之和尽可能大，但要求这个和必须是 k 的倍数。你能帮帮她吗？

输入描述：

第一行输入两个正整数 n  和 k

第二行输入 n 个正整数 ai

1≤n,k≤10^3

1≤ai≤10^10

输出描述：

如果没有合法方案，输出 -1。
否则输出最大的和。

---

题目解析

• 状态定义：首先定义一个二维dp数组，dp[i][j]表示前i个数中除以k的余数为j的当前最大和。
• 状态初始化：0个数时，最大和必为0，所以dp[0][0]=0。
• 状态转移：如果前一个状态余数为j，则更新当前余数为(j+arr[i])%k的情况，要么从余数为j的状态转化过来，要么前一个状态余数也是(j+arr[i])%k，即不选择当前元素。所以dp[i][(int)((j+arr[i])。

C++代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;signed main() // 01背包+同余
{int n = 0, k = 0;cin >> n >> k;vector<int> arr(n + 1);for (int i = 1; i <= n; ++i){cin >> arr[i];}vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, -INF));// dp[i][j]表示从1到i中选，总和 %k 等于j时，最大和是多少dp[0][0] = 0;for (int i = 1; i <= n; ++i){for (int j = 0; j < k; ++j){dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - arr[i] % k + k) % k] + arr[i]);}}cout << (dp[n][0] <= 0 ? -1 : dp[n][0]) << endl;return 0;
}

Java代码

import java.util.*; 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(), k = in.nextInt();long[] a = new long[n + 1];for(int i = 1; i <= n; i++){a[i] = in.nextLong();}long[][] dp = new long[n + 1][k];for(int i = 0 ; i <= n; i++){for(int j = 0; j < k; j++){dp[i][j] = (long)-1e16;}}dp[0][0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j < k; j++){dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(int)((j - a[i] % (long)k + (long)k) % (long)k)] + a[i]);}}if(dp[n][0] > 0)System.out.println(dp[n][0]);elseSystem.out.println(-1);}
}