当前位置:编程语言->C++语言 ->C++题解:P1164 小A点菜

原创版权标志C++题解:P1164 小A点菜

作者:张恩域  发表时间:2018/2/8 22:14:01  阅读:
[摘要] 这是一道简单的动规题,定义f[i][j]为用前i道菜用光j元钱的办法总数, 其状态转移方程如下:(1)if(j==第i道菜的价格)f[i][j]=f[i-1][j]+1 ;(2)if(j>第i道菜的价格) f[i][j]=f[i-1][j]+f[i-1][j-第i道菜的价 格];(3)if(j<第i道菜的价格) f[i][j]=f[i-1][j];……………………
广告招租:800元/月,QQ:1162839541
/*     P1164 小A点菜
题目背景
uim神犇拿到了uoi的ra(镭牌)后,立刻拉着基友小A到了一家……餐馆,
很低端的那种。uim指着墙上的价目表(太低级了没有菜单),说:“随便
点”。
题目描述
不过uim由于买了一些辅(e)辅(ro)书,口袋里只剩M元(M<=10000)。
餐馆虽低端,但是菜品种类不少,有N种(N<=100),第i种卖ai元(ai<=1
000)。由于是很低端的餐馆,所以每种菜只有一份。小A奉行“不把钱吃光
不罢休”,所以他点单一定刚好吧uim身上所有钱花完。他想知道有多少种
点菜方法。由于小A肚子太饿,所以最多只能等待1秒。
-------------------------题目分割线-------------------------------------------------
-------------------------题目分割线-----------------------------------------------
-------------------------题目分割线-------------------------------------------------
这是一道简单的动规题,定义f[i][j]为用前i道菜用光j元钱的办法总数,
其状态转移方程如下:(1)if(j==第i道菜的价格)f[i][j]=f[i-1][j]+1
;(2)if(j>第i道菜的价格) f[i][j]=f[i-1][j]+f[i-1][j-第i道菜的价
格];(3)if(j<第i道菜的价格) f[i][j]=f[i-1][j];说的简单一些,这三
个方程,每一个都是在吃与不吃之间抉择。若钱充足,办法总数就等于吃这
道菜的办法数与不吃这道菜的办法数之和;若不充足,办法总数就只能承袭
吃前i-1道菜的办法总数。依次递推,在最后,我们只要输出f[n][m]的值即
可。
*/ 
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[101],f[101][10001]={0};
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]+1;
          if(j>a[i]) f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
          if(j<a[i]) f[i][j]=f[i-1][j];
      }
    cout<<f[n][m];
    return 0;
}
文章来源:C++技术网原创文章版权为网站和作者共同所有,会员文章禁止转载。非会员文章转载做好本文超链接即表示授权转载。通过文章下面的分享按钮可以自由分享所有文章。

返回顶部

在线提问
问题标题:
问题描述:(简陋的描述会导致问题被最后回答、没有针对性回答甚至无法解答。请确保问题描述的足够清楚。)