动态规划之小A点菜

我会带着你远行 2022-05-04 11:00 159阅读 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 条评论，159人围观）

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

相关阅读

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

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

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

相关动态规划算法——知识点总结

动态规划算法通常用于求解具有最优性质的问题基本概念动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，

Myth丶恋晨/ 2023年10月17日 13:02/ 0 赞/ 87 阅读

相关算法-动态规划-新21点

算法-动态规划-新21点 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/new-21-game/ 1.

傷城~/ 2023年02月14日 13:29/ 0 赞/ 100 阅读

相关 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 赞/ 138 阅读

相关洛谷P1164 小A点菜

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

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

相关动态规划之小A点菜

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

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

相关 PAT A1030 动态规划

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

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

相关 P1164 小A点菜

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

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

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

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

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

相关 Luogu 1164 小A点菜

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

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