小A点菜（洛谷P1164题题解，Java语言描述）_星拱北辰的博客-程序员宅基地

技术标签： 算法  java  动态规划求解  动态规划  # OJ-LuoGu  algorithm  

题目要求

题目链接

在这里插入图片描述

分析

用 D P DP DP做是必然的，讲讲二维的吧：
f [ i ] [ j ] f[i][j] f[i][j]：用前 i i i道菜用光 j j j元钱的可能组合数
剩下的钱等于第 i i i道菜的价格时， f [ i ] [ j ] = f [ i − 1 ] [ j ] + 1 f[i][j]=f[i-1][j]+1 f[i][j]=f[i−1][j]+1
剩下的钱大于第 i i i道菜的价格时， f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − v [ i ] ] f[i][j]=f[i-1][j]+f[i-1][j-v[i]] f[i][j]=f[i−1][j]+f[i−1][j−v[i]]
剩下的钱小于第 i i i道菜的价格时， f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j]=f[i-1][j] f[i][j]=f[i−1][j]

可以压缩为一维 D P DP DP： f [ j ] + = f [ j − v [ i ] ] f[j]+=f[j-v[i]] f[j]+=f[j−v[i]]
解读为：当前花费情况下的点菜可能数，对于每道菜，包含点这个菜和不点这个菜的两种可能数之和。

AC代码（Java语言描述）

import java.io.IOException;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) throws IOException {
    
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
    
            nums[i] = scanner.nextInt();
        }
        scanner.close();
        int[] result = new int[m+1];
        result[0] = 1;
        for (int i : nums) {
    
            for (int j = m; j >= i; j--) {
    
                result[j] += result[j-i];
            }
        }
        System.out.println(result[m]);
    }
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_43896318/article/details/105916749

智能推荐

java中调用dos_JAVA如何调用DOS命令_weixin_39766109的博客-程序员宅基地

用Java编写应用时，有时需要在程序中调用另一个现成的可执行程序或系统命令，这时可以通过组合使用Java提供的Runtime类和Process类的方法实现。下面是一种比较典型的程序模式：...1 Process process = Runtime.getRuntime().exec(".//p.exe");23 process.waitfor( );...在上面的程序中，第一行的“.//p.exe...

计算机组成原理与系统结构实验指导书,计算机组成原理及系统结构实验指导书.pdf..._Flood Sung的博客-程序员宅基地

计算机组成原理及系统结构实验指导书目 录目 录 I第一部分 基本单元实验 - 1 -1.1 算术逻辑运算实验 - 1 -一、实验目的 - 1 -二、实验内容 - 1 -三、实验仪器 - 1 -四、实验原理 - 1 -五、实验步骤 - 2 -六、实验报告 - 4 -七、实验思考题 - 4 -1.2 进位控制实验 - 5 -一、实验目的 - 5 -二、实验内容 - 5...

oppoa1计算机记录删了怎么办,捡到oppoA1怎么解锁_柯尼塞格dbd的博客-程序员宅基地

Q3：oppo手机a1功能多吗全新配色自然配色，自然出色。不论是深邃海洋的幽蓝，还是成熟樱桃的鲜红，亦或是圆润珍珠的亮白，在全新的 OPPO A1 上， 每一种颜色都令人怦然心动。内存存储更大，运行更快。OPPO A1 采用 4GB 运行内存和 64GB 存储空间的组合，配合先进的处理器和软件优化，带来更快的运行速度。小蛮腰设计轻薄腰身，手感更惊艳。传承自 R 系列的轻薄设计，我们在 OPPO A...

Spring Cloud中遇到的Error creating bean with name 'hystrixCommandAspect' defined in class path resource_xianshigudu的博客-程序员宅基地

Error starting ApplicationContext. To display the auto-configuration report re-run your application with ‘debug’ enabled.2019-02-11 22:54:44.521 ERROR 5060 —[...

mac:在当前文件夹打开terminal终端_放错位的天才的博客-程序员宅基地

System Preferences -&gt; Keyboard -&gt; Shortcuts -&gt; Services -&gt; New Terminal at Folders/New Terminal Tab at Folder 这二项都勾上然后在Finder中,在任何目录上右击-&gt;service就能看到进入terminal的选项转载于:https://www.c...

video 满屏显示_HTML5 video播放器全屏(fullScreen)方法实例_weixin_39989159的博客-程序员宅基地

首先来说，这个标题具有误导性，但这样设置改标题也是主要因为video使用的比较多在html5中，全屏方法可以适用于很多html 元素，不仅仅是video复制代码代码如下:全屏问题*{padding: 0px;margin: 0px;}body div.videobox{width: 400px;height: 320px;margin: 100px auto;background-color:#0...

随便推点

linux脚本if then,shell脚本：使用if-then语句和test命令_weixin_39623273的博客-程序员宅基地

1、基本结构化命令if-then语句格式：if commandthencommandfibash shell的if语句会运行if后面的那个命令。若是该命令的退出状态码是0(该命令成功运行)，位于then部分的命令就会被执行。若是该命令的退出状态码是其余值，then部分的命令就不会被执行。fi语句用来表示if-then语句到此结束。web#! /bin/bashif pwdthenecho "it...

java swing单选按钮_JAVA Swing 获取单选按钮的值，复选框的值_weixin_39939661的博客-程序员宅基地

这是我自己写的一个测试程序，要求在点击“提交”按钮时，在监听事件中获取单选按钮的值，和复选框的值packagehelloworld;importjava.awt.*;importjavax.swing.*;importcom.borland.j...这是我自己写的一个测试程序，要求在点击“提交”按钮时，在监听事件中获取单选按钮的值，和复选框的值package helloworld;import j...

100本名著浓缩成了100话（转载）_塔山上的山的博客-程序员宅基地

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><font color="#9400D3">1．将感情埋藏得太深有时是件坏事。如果一个女人掩饰了对自己所爱的男子的感情，她也许就失去了得

山沟沟里的技术脱贫：阿里工程师助平武蜂农物联网养蜂 ..._weixin_34088583的博客-程序员宅基地

四川平武，数百年来以高山蜂蜜闻名。在海拔数千米的高山上，蜂农挖开树槽，用一种不喂食、天然的古法养蜂，蜜蜂汲取平武大山深处的黄连、朴厚、乌柏、五倍子、野菊花等上百种中草药花作为蜜源，酿出的蜂蜜更具营养价值。为了取得最纯正的蜂蜜，养蜂人从不进行人工干预，每年只取一次蜜。但极少有人知道平武人养蜂的辛苦，因为这山，实在太高，平武的海拔平均在2200-3000...

C# ConcurrentQueue （线程安全）_小兜全糖（Cx）的博客-程序员宅基地_c# concurrentqueue

http://dotnetpattern.com/csharp-concurrentqueueAdd Items in ConcurrentQueueIt provides an Enqueue method to add any item at the end of the queue. Enqueue takes the argument which data type matches with the type argument. Below is the example.ConcurrentQ

java mongodb 大于_解决MongoDB 排序超过内存限制的问题_有栖部羅援時的博客-程序员宅基地

对集合执行一个大排序操作(如聚合)，出现以下错误：(测试版本：MongoDB 3.0.6)&gt; db.bigdata.aggregate({$group : {_id : "$range", total : { $sum : 1 }}},{$sort : {total : -1}});#...aggregate failedat Error ()at doassert (src/mongo/s...

推荐文章

热门文章

相关标签