07 P1164 小A点菜

题目：

代码：

#include<iostream>
using namespace std;
/*
共m元，n种菜
f[i][j],前i道菜为购买范围，花完j元的可能性（不一定要全吃，是指在这个范围内）
a[i] 第i个菜的价钱
*/
2
int a[101],f[101][1001]={0};
/**/
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}//枚举前i个菜的选择空间，花光j元钱的可能性for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//假如第i道菜是便宜的，那么买它（其他菜任意）+不买它（同上！！！）==将它纳入购买范围的可能性if(j>a[i])f[i][j]=f[i-1][j]+f[i-1][j-a[i]];//在前i个范围不买它f[i][j]=在前i个范围买f[i-1][j]//在前i个范围买它f[i][j]==在前i-1个范围只花j-a[i]的钱//想一想条件概率公式if(j==a[i])f[i][j]=f[i-1][j]+1;//买它只有1种可能了if(j<a[i])f[i][j]=f[i-1][j];//不能买它}}cout<<f[n][m];}