3
#yyds干货盘点# 动态规划专题：删除相邻数字的最大分数
source link: https://blog.51cto.com/u_15488507/5824134
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.简述：
描述给定一个长度为 n 的仅包含正整数的数组，另外有一些操作，每次操作你可以选择数组中的任意一个元素 ，同时数组中所有等于
和
的元素会被全部移除，同时你可以得到
分，直到所有的元素都被选择或者删除。请你计算最多能得到多少分。数据范围： 数组长度满足
，数组中的元素大小都满足
第一行输入一个正整数 n 表示数组的长度
第二行输入 n 个数字表示数组的各个元素值。
输出描述：输出能得到的最大分数。
示例1直接选择元素 2 ，然后 1 被同时移除。
先选择 3 ，同时 2 被移除，再选择 1 ，即得到 4 分。
9
1 2 1 3 2 2 2 2 3
1 2 1 3 2 2 2 2 3
第一步选择一个 2 ，然后所有 1 和 3 都被移除了，此时数组中剩下的是 [2,2,2,2] ，依次选择他们即可得到 10 分
2.代码实现：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int[] p = new int[n];
for (int i = 0; i < n; i++) {
p[i] = reader.nextInt();
}
int[] dp = new int[10001];
int[] trans = new int[10001];
for (int i = 0; i < p.length; i++) {
trans[p[i]] += p[i];
}
dp[0] = 0;
dp[1] = trans[1];
for (int i = 2; i < trans.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + trans[i]);
}
System.out.println(dp[dp.length - 1]);
}
}
public class Main {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int[] p = new int[n];
for (int i = 0; i < n; i++) {
p[i] = reader.nextInt();
}
int[] dp = new int[10001];
int[] trans = new int[10001];
for (int i = 0; i < p.length; i++) {
trans[p[i]] += p[i];
}
dp[0] = 0;
dp[1] = trans[1];
for (int i = 2; i < trans.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + trans[i]);
}
System.out.println(dp[dp.length - 1]);
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK