3
#yyds干货盘点# 动态规划专题：小红取数
source link: https://blog.51cto.com/u_15488507/5868896
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 动态规划专题：小红取数
精选 原创1.简述：
描述小红拿到了一个数组，她想取一些数使得取的数之和尽可能大，但要求这个和必须是 的倍数。你能帮帮她吗？
第一行输入两个正整数 和
第二行输入 个正整数
如果没有合法方案，输出 -1。否则输出最大的和。
示例15 5
4 8 2 9 1
4 8 2 9 1
取后四个数即可
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]);
}
}
}
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]);
}
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK