动态规划之小A点菜

我会带着你远行 2022-05-04 11:00 200阅读 0赞

## 题目背景 ##

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

`uim`指着墙上的价目表（太低级了没有菜单），说：“随便点”。

## 题目描述 ##

不过`uim`由于买了一些`辅（e）辅（ro）书`，口袋里只剩MMM元(M≤10000)(M \\le 10000)(M≤10000)。

餐馆虽低端，但是菜品种类不少，有NNN种(N≤100)(N \\le 100)(N≤100)，第iii种卖aia\_iai元(ai≤1000)(a\_i \\le 1000)(ai≤1000)。由于是很低端的餐馆，所以每种菜只有一份。

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

由于`小A`肚子太饿，所以最多只能等待111秒。

## 输入输出格式 ##

**输入格式：**

第一行是两个数字，表示NNN和MMM。

第二行起NNN个正数aia\_iai（可以有相同的数字，每个数字均在100010001000以内）。

**输出格式：**

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

## 输入输出样例 ##

**输入样例\#1：** 复制

4 4
    1 1 2 2

#include<bits/stdc++.h>
    using namespace std;
    int m,n,v[105],f[105][10005],sum=0;//m是总钱，n是菜的种类
    int main(){         
        cin>>n>>m;
        for(int i=0;i<n;i++)cin>>v[i];
        for(int i=0;i<n;i++)
            for(int j=1;j<=m;j++)
                if(j==v[i]) f[i+1][j]=f[i][j]+1;   
                else if(j>v[i]) f[i+1][j]=f[i][j]+f[i][j-v[i]];//如果钱充足的话，那么f[i][j]就等于吃这盘菜和不吃这盘菜的方法之和  
                else    f[i+1][j]=f[i][j]; 
        cout<<f[n][m];
    }

代码虽然简单，但是思路复杂。要求的是把所有钱都花完的策略。

一开始想的办法是搜索，就随手打了一个dfs，但是结果是14，原因是因为神搜会有重复的序列。

然后想到了动态规划。

对每道菜进行一次金钱遍历。

如果金钱等于菜价，即恰好花完，则方案数加1

如果金钱大于菜价，则方案数是不吃这道菜和吃这道菜的方法之和，

如果金钱小于菜价，则方案数是不吃的方法和。

发表评论取消回复

表情：

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

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

相关阅读

相关动态规划之下降路径最小和

1. 题目分析题目链接选自力扣 : [下降路径最小和][Link 1] ![image.png][] 如果光看这个题目说明的话, 是有点抽象的. 我们结合实例

╰半夏微凉°/ 2024年03月16日 22:48/ 0 赞/ 94 阅读

相关动态规划之最小路径和

1. 题目分析题目链接选自力扣 : [最小路径和][Link 1] ![image.png][] 前面解触了很多路径题. 这依然是一个路径题, 题目要求从左上角

深碍√TFBOYSˉ_/ 2024年03月16日 22:48/ 0 赞/ 54 阅读

相关【算法小课堂】动态规划

动态规划动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。网上也

桃扇骨/ 2024年02月05日 23:04/ 0 赞/ 41 阅读

相关 A Mini Locomotive【简单动态规划】

A Mini Locomotive > A train has a locomotive that pulls the train with its many passe

桃扇骨/ 2022年06月01日 11:05/ 0 赞/ 196 阅读

相关洛谷P1164 小A点菜

题目背景 uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。 uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。题

曾经终败给现在/ 2022年05月28日 07:10/ 0 赞/ 193 阅读

相关动态规划之小A点菜

题目背景 `uim`神犇拿到了`uoi`的`ra`（镭牌）后，立刻拉着基友`小A`到了一家……餐馆，很低端的那种。 `uim`指着墙上的价目表（太低级了没有菜单），说：

我会带着你远行/ 2022年05月04日 11:00/ 0 赞/ 201 阅读

相关 PAT A1030 动态规划

![clipboard.png][] 这道题是动态规划几大问题的其中一种，为最长回文子串问题；动态规划个人来说，觉得最重要的就是建立状态转移方程。对于方程变量，我认为最

拼搏现实的明天。/ 2022年03月07日 12:50/ 0 赞/ 139 阅读

相关 P1164 小A点菜

题目描述：不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩MMM元(M≤10000)(M \\le 10000)(M≤10000)。餐馆虽低端，但是菜品种类不

忘是亡心i/ 2022年02月28日 04:16/ 0 赞/ 178 阅读

相关动态规划-从菜鸟到老鸟

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 前言最近在牛客网上做了几套公司的真题，发现有关动

痛定思痛。/ 2022年01月14日 01:07/ 0 赞/ 325 阅读

相关 Luogu 1164 小A点菜

终于在任重而道不远的形势的逼迫下，拾起了自己畏惧的动态规划。于是开始从最简单的题做起。题目链接：[https://www.luogu.org/problemnew/sh

电玩女神/ 2021年12月10日 05:47/ 0 赞/ 219 阅读