动态规划-FATE

客官°小女子只卖身不卖艺 2023-07-18 14:09 12阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]  
Sample Input

10 10 1 10
    1 1
    10 10 1 9
    1 1
    9 10 2 10
    1 1
    2 2

Sample Output

0
    -1
    1

import java.util.*;
    
    public class ll {
        
       public static void main(String[] args) {
        
            int[] a=new int[110];
            int[] b=new int[110];
            int[][] dp=new int[110][110];
            Scanner scanner=new Scanner(System.in);
            while(true){
        
                int n=scanner.nextInt();
                int m=scanner.nextInt();
                int k=scanner.nextInt();
                int s=scanner.nextInt();
                for (int i = 1; i <=k ; i++) {
        
                    a[i]=scanner.nextInt();//加的经验值
                    b[i]=scanner.nextInt();//减的忍耐度
                }
                int ans=-1;
                for (int i = 1; i <=m ; i++) {
        //保留的忍耐程度
                    for (int j = 1; j <=k ; j++) {
        //怪的种数
                        for (int l = 1; l <=s ; l++) {
        //最多杀怪数
                            if (i>=b[j]){
        
                                dp[i][l]=Math.max(dp[i][l],dp[i-b[j]][l-1]+a[j]);
                                //dp[i][l]在剩下的i忍耐程度下，最多杀怪数加的经验值
                            }
                        }
                    }
                    if (dp[i][s]>=n) {
        
                        ans=m-i;
                        break;
                    }
                }
                System.out.println(ans);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: /images/20230528/0d1614d86b0e48a09cedabbbf9aeee8f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划-FATE

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

客官°小女子只卖身不卖艺/ 2023年07月18日 14:09/ 0 赞/ 13 阅读

相关动态规划

一：概念：和分冶法相似，不同之处在于前者是把问题划分为互不相交的子问题，而动态规划会出现子问题重叠的情况。通常用来求解最优化问题。。基本步骤： ①：刻画一个最优

我就是我/ 2022年12月01日 11:51/ 0 赞/ 70 阅读

相关动态规划

-------------------- 动态规划的设计思想动态规划（DP）\[1\]通过分解成子问题解决了给定复杂的问题，并存储子问题的结果，以避免再次计算相同的结

柔情只为你懂/ 2022年09月25日 11:15/ 0 赞/ 290 阅读

相关动态规划

作者：Hawstein 出处： [http://hawstein.com/posts/dp-novice-to-advanced.html][http_hawstein.c

淡淡的烟草味﹌/ 2022年09月24日 12:17/ 0 赞/ 244 阅读

相关动态规划

1. 首先，动态规划不是一个特定的算法，它代表的是一种思想，一种手段 2. 动态规划方法往往用于求解“最优化问题”，能用动态规划求解的问题的前提是问题具有“最优子结构性质”

刺骨的言语ヽ痛彻心扉/ 2022年07月29日 11:46/ 0 赞/ 140 阅读

相关动态规划

首先是概念:动态规划就是将原问题划分为简单的几个小问题（有点类似与分治法?但是分治法中的各个小问题是相互独立的，彼此之间不会产生影响，但是动态规划中所得的值和前面相关，当前的解

青旅半醒/ 2022年07月12日 05:01/ 0 赞/ 355 阅读

相关动态规划

基本思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。区别：与

ゞ浴缸里的玫瑰/ 2022年05月25日 09:44/ 0 赞/ 479 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 369 阅读

相关动态规划

1.题目：最长递增子序列（Longest Increasing Subsequence）问题描述： > 给定长度为N的数组A，计算A的最长单调递增的子序列（不一定连续）

妖狐艹你老母/ 2022年05月11日 04:56/ 0 赞/ 317 阅读

相关动态规划

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/7519359

左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 548 阅读