题意整理。 给定一个数组，数组中所有元素均大于0。 现在要从数组中取出一些元素，使得和最大，并且和是k的倍数。求满足要求的最大和是多少。 方法一（二维dp） 1.解题思路 状态定义：首先定义一个二维dp数组，dp[i][j]表示前i个数中除以k的余数为j的当前最大和。 状态初始化：0个数时，最
展开全文
看了大佬们写的没有看懂，自己写了半天，虽然是用时最多的还是要记录一下，并送给大家参考。
问题要点是dp数组如何构建、dp[i][j] 的含义、转移方程如何写。
dp数组如何构建：我以需计算的列表长度n为列，在此基础上添加一列辅助列，代表未取元素时的状态。以对数字K取模后的可能性为行，示例**
展开全文
/*
集合：前i个数组中选择一些数 并且 这些数的和必须是k的倍数的方案
属性：求最大
状态定义：dp[i][j]表示前i个数中，选择一些数的和对k取余为j
状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][(j+nums[i])%k]+nums[i])
*/
impo
展开全文
小红取数
难度：3星
首先第一个想法是，开一个dp数组，dp[i]dp[i]dp[i] 代表取前i个数的最大值。
那么dp[i]怎么求呢？很明显，如果要取了第 iii 个数 a[i]a[i]a[i] ，满足和能被k整除，那么就有个限制：前i-1个数里，满足取的数之和除以k的余数为 k−a[i]k-a
展开全文
这道题的思路与背包问题有些许相似。转移方程是df[i][(j+arr[i])%k]=max(df[i-1][j]+arr[i],df[i-1][(j+arr[i])%k])。其中df[i][j]表示添加第i个数时对k取模得j的最大和。在实现时考虑是否能像背包问题一样，仅使用一维数组，通过遍历的顺序来
展开全文
思路解析：
如何想到动态规划的递推式是最重要的。
1.如果我们采取一维的数组，那么没法同时满足两个条件。所以采取二维数组进行数据的存储。
2.利用dp[i][j],将第一个i表示前i个数值，j表示前i个数值modk后的余数值。而dp[i][j]整体表示前i个数值在余j时的最大值，而我们需要获得的是d
展开全文
#include <iostream>
#include <bits/stdc++.h> // 包含所有标准库
using namespace std;
int main() {
int n, k; // n 表示数组的大小，k 表示取模的值
long lo
展开全文
import java.io.;
import java.util.;
public class Main{
//dp代表和
static long[][]dp;
static int k;
public static void main(String[] args)throws IOExcepti
展开全文
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e3 + 5;
int f[MAXN],dp[MAXN][MAXN];;
signed main()
{
展开全文
水题，考虑dp[i][j] 为：考虑到第 i 个数，模 k 余 j 的最大选数方案即可，转移是显然的，注意边界即可。
#include<bits/stdc++.h>
using i64 = long long;
int main() {
std::cin.tie(nullptr
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
