P1164 小A点菜

这篇具有很好参考价值的文章主要介绍了P1164 小A点菜。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目背景

uim 神犇拿到了 uoi 的 ra(镭牌)后,立刻拉着基友小 A 到了一家……餐馆,很低端的那种。

uim 指着墙上的价目表(太低级了没有菜单),说:“随便点”。

题目描述

不过 uim 由于买了一些书,口袋里只剩 M 元(M≤10000)。

餐馆虽低端,但是菜品种类不少,有 N 种 (N≤100),第 i 种卖ai​ 元 (ai​≤1000)。由于是很低端的餐馆,所以每种菜只有一份。

小 A 奉行“不把钱吃光不罢休”,所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。

由于小 A 肚子太饿,所以最多只能等待 11 秒。

输入格式

第一行是两个数字,表示 N 和 M。

第二行起 N 个正数 ai​(可以有相同的数字,每个数字均在 1000 以内)。

输出格式

一个正整数,表示点菜方案数,保证答案的范围在 int 之内。

输入输出样例

输入 

4 4
1 1 2 2

输出 文章来源地址https://www.toymoban.com/news/detail-623983.html

3

方程 f[i,j]:=f[i-1,j]+f[i-1,j-a[i]];

数组表示在前i道菜中,总价格为j。

你可以不点这道菜(f[i-1,j]),或者点(f[i-1,j-a[i]])

二维代码实现

#include<iostream>
using namespace std;
const int N=110;
int a[N];
int f[N][10064];  //数组表示在前i道菜中,总价格为j。

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j<a[i])           //钱不够,不点
			f[i][j]=f[i-1][j];
			if(a[i]==j)     //钱刚好够,点
			f[i][j]=f[i-1][j]+1;
			if(j>a[i])                 //钱还有多余,点+不点 
			f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
		}
	} 
	cout<<f[n][m]<<endl;
	return 0;
}

一维代码实现

#include<iostream>
using namespace std;
const int N=110;
int a[N];
int f[10064]; 

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	f[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=a[i];j--){
			f[j]=f[j]+f[j-a[i]];
		}
	} 
	cout<<f[m]<<endl;
	return 0;
}

到了这里,关于P1164 小A点菜的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ( 动态规划) 1035. 不相交的线 ——【Leetcode每日一题】

    难度:中等 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足: nums1[i] == nums2[j] 且绘制的直线不与任何其他连线(非水平线)相交。 请注意,连线即使在端点也不能相交

    2024年02月05日
    浏览(44)
  • 【Leetcode每日一题】 动态规划 - 地下城游戏(难度⭐⭐⭐)(61)

    1. 题目解析 题目链接:174. 地下城游戏 这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。 2.算法原理 一、状态表定义 在解决地下城游戏问题时,我们首先需要对状态进行恰当的定义。一个直观的想法是,从起点开始,到达[i, j]位置时所需的最低初始

    2024年04月29日
    浏览(44)
  • ( 动态规划) 516. 最长回文子序列 ——【Leetcode每日一题】

    难度:中等 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = “bbbab” 输出:4 解释:一个可能的最长回文子序列为 “bbbb” 。 示例

    2024年02月06日
    浏览(44)
  • (动态规划) 132. 分割回文串 II ——【Leetcode每日一题】

    难度:困难 给你一个字符串 s ,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 示例 2: 输入:s = “a” 输出:0 示例 3: 输入:

    2024年02月15日
    浏览(46)
  • [Week 19]每日一题(C++,数学,并查集,动态规划)

    目录 [Daimayuan] T1 倒数第n个字符串(C++,进制) 输入格式 输出格式 样例输入 样例输出 解题思路 [Daimayuan] T2 排队(C++,并查集) 输入格式 输出格式 样例输入1 样例输出1 样例输入2 样例输出2 样例输入3 样例输出3 数据规模 解题思路 [Daimayuan] T3 素数之欢(C++,BFS) 数据规模

    2024年02月02日
    浏览(52)
  • 【每日一题 | 动态规划】访问完所有房间的第一天

    【动态规划】【数组】【2024-03-28】 1997. 访问完所有房间的第一天 定义状态 定义 f[i] 表示第一次到达房间 i 的日期编号。 根据题意,首次(第 1 次)访问房间 i 时,因为 1 是计数,所以下一次一定会访问房间 j = nextVisit[i] 。只有访问次数达到偶数才能访问右边的下一个房间

    2024年04月16日
    浏览(38)
  • [Week 18] 每日一题(C++,动态规划,线段树,数学)

    目录 [Daimayuan] T1 最长公共子序列(C++,DP,二分) 输入格式 输出格式 数据范围 输入样例 输出样例 解题思路 [Daimayuan] T2 喵喵序列(C++,序偶) 题目描述 输入格式 输出格式 样例输入 样例输出 样例说明 数据范围 双倍经验 解题思路: [Daimayuan] T3 漂亮数(C++,字符串) 输入

    2023年04月24日
    浏览(59)
  • 【每日一题】ABC248C - Dice Sum | 动态规划 |简单

    原题链接 构造一个长度为 n n n 的整数数组 a a a ,满足如下两个条件: 1 ≤ a i ≤ m 1leq a_ileq m 1 ≤ a i ​ ≤ m ∑ a i ≤ k sum a_ileq k ∑ a i ​ ≤ k 问可以构造出多少种不同的数组 a a a 。 1 ≤ n , m ≤ 50 1leq n,mleq 50 1 ≤ n , m ≤ 50 n ≤ k ≤ n × m nleq kleq ntimes m n ≤ k ≤ n × m

    2024年02月09日
    浏览(38)
  • DP算法:动态规划算法

    (1)确定初始状态 (2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来 (3)确定边界条件。 蓝桥杯——印章(python实现) 使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率 i表示买的印章数,j表示凑齐的印章种数 情况一:如果ij,不可能凑齐印章,概

    2024年02月07日
    浏览(51)
  • (动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】

    难度:简单 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n) 。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 提示 : 1 = a r r . l e n g t h = 1 0 5 1 = arr.length = 10^

    2024年02月11日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包