小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]);
}
}
智能推荐
对于verlog仿真的时候，数据打拍delay的问题_verilog打拍_ronaldo_hu的博客-程序员宅基地
这几天对于verlog里面reg变量赋值，导致数据delay的情况十分混论，这里理一理; 首先单独一个reg型变量在always块中，进行常数赋值或者自赋值，显然不会产生delayalways@( posedge clk or negedge rst_n )begin if( !rst_n )begin count_reg <= 0; end else
290种零食大统计，谁能唤起80、90后的童年回忆？|数据会说话_csdn业界要闻的博客-程序员宅基地
戳蓝字“CSDN云计算”关注我们哦！数据分析：喜欢果脯的朱小五内容撰写：只爱辣条的王小九本文转自公众号『凹凸数读』1块钱能买到什么？对于80、90后的童年来讲，1块钱是4...
Gotomeeting在视频会议行业的应用趋势分析_u014749660的博客-程序员宅基地
近年来，视频会议凭借在网络通讯方面的巨大优势，已成为商务会议的首选，迅速在各大企业中普及。不仅如此，视频会议正迅速与3G、物联网、云计算这些热门运用相融合，其应用呈现出更广泛、更深入等众多新特点。 应用范围稳步扩大 随着技术的不断发展，视频会议软件已一举突破网络带宽、互联互通性、稳定性等瓶颈，以更为稳定、灵活、快捷、方便的方式迅速取代硬件视频会议，成为行业主流应用。
Could not load java.net.BindException异常的解决办法_福龟大大的博客-程序员宅基地
系统配置， MyEclipse6.5+tomcat6.0+MySQL+Struts2症状如下： 在启动 tomcat ，并发布应用后没有问题，但是如果重新发布就出现如下异常：this web application instance has been stopped alre
signature=fe1aabef3439a54d34c395244cc46932,Added ISOWeek to System.Globalization_weixin_39957271的博客-程序员宅基地
Commit list for mono/corert:* mono/[email protected] [Number] make double 0.0 cmp more portable (#30)* mono/[email protected] Update ISOWeek.cs* mono/[email protected] fix ISOWeek for mcs* mono/[email protected]...
机器学习实战之决策树熵的概述_决策树 熵_user_zongji的博客-程序员宅基地
机器学习实战之决策树熵的概述一、决策树简介二、决策树的一般流程三、决策树构建的准备工作1、特征选择（1）香农熵（2）编写代码计算经验熵一、决策树简介决策树是什么？自己理解:决策树是一颗能给人们带来决策的树,它将根据提供的可能条件,构建一颗树的模型,其中条件即树的枝干,可能性越强,枝干将会长得越茂盛,反之就越秃.书中解释:决策树(decision tree)是一种基本的分类与回归方法。举个通俗易懂的例子，如下图所示的流程图就是一个决策树，长方形代表判断模块(decision block)，椭圆形成
随便推点
电力系统潮流计算中的导纳矩阵计算，matlab源程序_潮流计算中导纳矩阵的计算 程序_山高一小的博客-程序员宅基地
电力系统导纳矩阵计算，MATLAB这学期在上大四专业选修课时，一个课后作业是写一个电力系统的导纳矩阵计算程序，我找了找资料肝了半天的程序如下图所示，希望能对大家有用。程序说明1.具有非标准变比的变压器处理如果变压器阻抗归算到非标准变比的K侧，则在参数输入脚本文件data中变压器参数第五列记为0；如果归算到非标准变比的1侧，则在参数输入脚本文件data中变压器参数第五列记为1。2.线路为双回线时，需要将两个节点之间线路阻抗减半，导纳加倍；同时，如果线路是双回线则在data线路参数中第五列记为1，否
使用ShaderGraph制作动漫人物眼睛部分_wakawaka555的博客-程序员宅基地
使用ShaderGraph制作动漫人物眼睛部分实现效果如下图：实现步骤：新建HDRP工程，创建Eye Graph(2019版还是处于预览版，正式项目慎用)节点图如下连接点这里就不详述了，官网上有详细的解释。2.人物模型使用资源为官方资源，百度链接如下：链接：https://pan.baidu.com/s/1K6SxpO7_PROLdAWKbPm5dw提取码：jkml3.新建Sample Texture 2D节点，然后创建两个Texture2D变量，分别显示眼睛和眼白图片：如上图所示，
html鼠标滚动效果代码,JS+CSS实现大气清新的滑动菜单效果代码_hi啊的博客-程序员宅基地
本文实例讲述了JS+CSS实现大气清新的滑动菜单效果代码。分享给大家供大家参考，具体如下：这是一款比较大气清新的滑动导航菜单，CSS和JavaScript配合完成，鼠标放到一级菜单上，会滑出二级的菜单，兼容性也不错，适合大多数网站使用，用到两张背景图片，请拷贝图片地址下载图片。运行效果截图如下：在线演示地址如下：具体代码如下：/p>"http://www.w3.org/TR/xhtml1/D...
java查询WFS服务_weixin_30511039的博客-程序员宅基地
在我们访问wfs服务时候，有时候会遇到前台访问时候的跨域问题。这里给出java访问的一个小例子。 1 import java.io.BufferedReader; 2 import java.io.IOException; 3 import java.io.InputStream; 4 import java.io.InputStreamReader; 5 imp...
trie图 java_【数据结构】之字典树（前缀树、Trie）_宁输输的博客-程序员宅基地
一、引言字典树是专门为字符串处理设计的，字典树可以做到查询每个条目的时间复杂度和字段中一共有多少条目无关，跟查询的字符串长度相关。1、什么是字典树字典树结构说明：上图表示的是一颗只存英文单词的字典树，假设只包含小写英文字母，以上字典树中存储了6个单词，每个节点可以有26个指向下个节点的指针二、实现基于TreeMap实现字典树import java.util.TreeMap;/*** 字典树、前缀树...
MeteoInfo-Micaps绘制色斑图_m0_61759012的博客-程序员宅基地
meteoInfo处理色斑图