洛谷P1164 小A点菜

曾经终败给现在 2022-05-28 07:10 178阅读 0赞

## 题目背景 ##

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

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

## 题目描述 ##

不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩M元（M<=10000）。

餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i种卖ai元（ai<=1000）。由于是很低端的餐馆，所以每种菜只有一份。

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

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

## 输入输出格式 ##

输入格式：

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

第二行起N个正数ai（可以有相同的数字，每个数字均在1000以内）。

输出格式：

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

![70][]

解法一：DFS

#include<iostream>
    using namespace std;
    
    int N, M;
    int menue[105];
    bool vis[105];
    int ans;
    void dfs(int now,int x)//now代表现在的钱数,x表示第几道菜
    {
    	if (now > M) return;//大于M就返回
    	if (now == M)
    	{
    		ans++;
    		//cout << M << ' ' << ans << endl;
    		return;
    	}
    	for (int i = x+1; i <= N; i++)//从第x道菜后面开始选择
    	if (!vis[i])
    	{
    		vis[i] = true;
    		//cout << now + menue[i] << endl;
    		dfs(now + menue[i],i);
    		vis[i] = false;
    	}
    }
    
    int main()
    {
    	//freopen("1.txt","r",stdin);
    	cin >> N >> M;
    	for (int i = 1; i <= N; i++)
    		cin >> menue[i];
    	dfs(0,0);//刚开始花0元选择第0道菜
    	cout << ans;
    	return 0;
    }

解法二：二维动态规划

参考题解：[https://www.luogu.org/blog/user31798/solution-p1164][https_www.luogu.org_blog_user31798_solution-p1164]

（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<iostream>
    using namespace std;
    
    int N, M;
    int menue[105];
    int dp[101][10010];
    
    int main()
    {
    
    	//freopen("1.txt", "r", stdin);
    	cin >> N >> M;
    	for (int i = 1; i <= N; i++)
    		cin >> menue[i];
    
    	for (int i = 1; i <= N; i++)
    	{
    
    		for (int j = 1; j <= M; j++)
    		{
    			if (j == menue[i]) dp[i][j] = dp[i - 1][j]+1;
    			else if (j > menue[i]) dp[i][j] = dp[i-1][j]+dp[i-1][j-menue[i]];
    			else dp[i][j] = dp[i-1][j];
    
    			//cout << dp[i][j] << ' ';
    		}
    		//cout << endl;
    	}
    	cout << dp[N][M];
    	return 0;
    }

解法三：一维动态规划

参考题解：[https://www.luogu.org/blog/user47149/solution-p1164][https_www.luogu.org_blog_user47149_solution-p1164]

由题意可以得到我们的状态转移f\[i\]+=f\[j-v\[i\]\]

#include<iostream>
    using namespace std;
    
    int N, M;
    int menue[105];
    int dp[10010];
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> N >> M;
    	for (int i = 1; i <= N; i++)
    		cin >> menue[i];
    	dp[0] = 1;
    	for (int i = 1; i <= N;i++)
    	for (int j = M; j >= menue[i]; j--)
    		dp[j] += dp[j - menue[i]];
    	cout << dp[M];
    	return 0;
    }

[70]: /images/20220528/1559ff8d9ad24636a1a77b5b9492f56c.png
[https_www.luogu.org_blog_user31798_solution-p1164]: https://www.luogu.org/blog/user31798/solution-p1164
[https_www.luogu.org_blog_user47149_solution-p1164]: https://www.luogu.org/blog/user47149/solution-p1164