P1705 爱与愁过火

· · 题解

题目分析：

从题目中不难发现，这道题可以用简单的背包DP来做。

思路：

先是定义状态：可以用 f(i,j,k) 表示，前 i 样菜品中，选择 j 道，价格为 k 的方案总数。

可以得出状态转移方程：

f(i,j,k) = f(i - 1,j,k) + f(i - 1,j - 1,k - x(i))

就是把选择与不选择的方案总数相加起来。

代码：

#include<bits/stdc++.h>
using namespace std;
int m, r, n;
int x[35], v;
int f[35][35][35 * 90 + 5], ans;
int main()
{
    cin>>m>>r>>n;
    f[0][0][0] = 1;
    for (int i = 1; i <= m; i++)
        cin>>x[i],f[i][0][0] = 1;//定义初始值
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= i; j++)//枚举物品放置的个数
        {
            for (int k = 1; k <= m * 90; k++)//枚举当前的价格
            {
                f[i][j][k] = f[i - 1][j][k];//不选择这个菜品
                if (k >= x[i]) f[i][j][k] += f[i - 1][j - 1][k - x[i]];//选择与防止越界
            }
        }
    }   
    for (int j = n + 1; j <= m * 90; j++)//去找大于n的，并累加起来
    {
            ans += f[m][r][j];  
    }
    cout<<ans;//直接输出
    return 0;
}