技术学习分享_一航技术 技术资讯 #yyds干货盘点# 动态规划专题:小红取数

#yyds干货盘点# 动态规划专题:小红取数

广告位

1.简述:

描述

小红拿到了一个数组,她想取一些数使得取的数之和尽可能大,但要求这个和必须是 #yyds干货盘点# 动态规划专题:小红取数 的倍数。你能帮帮她吗?

输入描述:

第一行输入两个正整数 #yyds干货盘点# 动态规划专题:小红取数 和 #yyds干货盘点# 动态规划专题:小红取数

第二行输入 #yyds干货盘点# 动态规划专题:小红取数 个正整数 #yyds干货盘点# 动态规划专题:小红取数

#yyds干货盘点# 动态规划专题:小红取数

#yyds干货盘点# 动态规划专题:小红取数

输出描述:

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

示例1

输入:

5 5
4 8 2 9 1

输出:

20

说明:

取后四个数即可

2.代码实现:

import java.util.*;

public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();

long[] arr=new long[n+1];
for(int i=1;i<=n;i++){
arr[i]=sc.nextLong();
}
//dp数组,dp[i][j]表示前i个数中除以k的余数为j的当前最大和
long[][] dp=new long[n+1][k];
for(int i=0;i<=n;i++){
Arrays.fill(dp[i],Long.MIN_VALUE);
}
//状态初始化,0个数时,最大和必为0
dp[0][0]=0;

for(int i=1;i<=n;i++){
for(int j=0;j<k;j++){
/*如果前一个状态余数为j,则更新当前余数为(j+arr[i])%k的情况,要么从余数为j的状态转化过来,
要么前一个状态余数也是(j+arr[i])%k,即不选择当前元素*/
dp[i][(int)((j+arr[i])%k)]=Math.max(dp[i-1][j]+arr[i],dp[i-1][(int)((j+arr[i])%k)]);
}
}

//如果小于等于0,说明不能由初始状态转化过来,没有合法方案
if(dp[n][0]<=0){
System.out.println(-1);
}
else{
System.out.println(dp[n][0]);
}


}

}
本文来自网络,不代表技术学习分享_一航技术立场,转载请注明出处。

作者: 一航技术

上一篇
下一篇
广告位

发表回复

返回顶部