C++题解:P1164 小A点菜

2018-02-08 22:14:01369人围观普通文章,仅限个人转载,一天数量不超过1篇,禁止商业平台转载,禁止采集,版权所有,违者必究。请按[超链接格式文本]转载:本文转载自:C++题解:P1164 小A点菜
简介这是一道简单的动规题,定义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];……………………
/*    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秒。
-------------------------题目分割线-------------------------------------------------
-------------------------题目分割线-----------------------------------------------
-------------------------题目分割线----------------------------
登陆系统,查看更多

阅读排行