蓝桥杯 算法提高 第二点五个不高兴的小明(动态规划) JAVA
2021/4/15 12:55:09
本文主要是介绍蓝桥杯 算法提高 第二点五个不高兴的小明(动态规划) JAVA,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题描述 有一条长为n的走廊,小明站在走廊的一端,每次可以跳过不超过p格,每格都有一个权值wi。小明要从一端跳到另一端,不能回跳,正好跳t次,请问他跳过的方格的权值和最大是多少? 输入格式 输入的第一行包含两个整数n, p, t,表示走廊的长度,小明每次跳跃的最长距离和小明跳的次数。
接下来n个整数,表示走廊每个位置的权值。 输出格式 输出一个整数。表示小明跳过的方格的权值和的最大值。 样例输入 8 5 3
3 4 -1 -100 1 8 7 6 样例输出 12 数据规模和约定 1<=n, p, t<=1000, -1000<=wi<=1000。 思路 本题动态规划,二维数组dp[i][j]用于存储第i次跳跃,跳到j位置上权重值和的最大值。
import java.util.*; public class 第二点五个不高兴的小明 { static int n,p,t; static int[] fangge; static int[][] dp; //dp[i][j]=k 表示第i步走到第j个位置有权重值和为K public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); n=scan.nextInt(); p=scan.nextInt(); t=scan.nextInt(); fangge=new int[n+2]; dp=new int[t+2][n+2]; for(int i=1;i<=n;i++) { fangge[i]=scan.nextInt(); } for(int i=1;i<=t;i++) { for(int j=0;j<=n;j++) { dp[i][j]=Integer.MIN_VALUE; } } for(int i=1;i<=p && i<=n;i++) { dp[1][i]=fangge[i]; } dp[0][0]=0; int step=2; while(step<t) { for(int index=step-1;index<=n;index++) { if(dp[step-1][index]==Integer.MIN_VALUE) continue; for(int i=1;i<=p;i++) { int newIndex=index+i; if(newIndex>n+1) continue; int temp=dp[step-1][index]+fangge[newIndex]; dp[step][newIndex]=Math.max(dp[step][newIndex], temp); } } step++; } int maxN=Integer.MIN_VALUE; for(int i=1;i<=n;i++) { if(dp[t-1][i]>maxN && i+p>=n+1) { maxN=dp[t-1][i]; } } System.out.println(maxN); } }
这篇关于蓝桥杯 算法提高 第二点五个不高兴的小明(动态规划) JAVA的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?