题解 P1164 【小A点菜】

HiroshiRealm · 2018-04-22 18:33:12 · 题解

本蒟蒻没有学过dp（多喽哦），只好用dfs水一水，结果竟然水过去了（滑稽）

好了，进入正题（敲黑板）

我们知道，dfs是穷举每一种可能，也就是打暴力，但是一般的题目不会让你打暴力过的，所以一般都要剪枝，这题也不例外

首先，我们可以用sort排序，确定单调性，有助于下面的剪枝

点菜，也就是说每一个菜都有选和不选两种可能，如果剩余钱数不够，就必须不选

因此，由于之前我们确定了单调性，所以只要前面的这一种菜就已经钱数不够了，后面的就一定不够，就可以直接返回

上代码

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include <iostream>
using namespace std;
int a,b,c[10000],sum,ans;
inline void dfs(int step,int money){//money为剩余钱数
    if(money==0){//满足条件
        ans++;return ;
    }
    if(step==a+1)return;//已经是最后一个菜
    if(money>=c[step]){//钱还够
        dfs(step+1,money-c[step]);
        dfs(step+1,money);
    }
    else return ;//没钱了，就直接返回
}
int main() {
    scanf("%d%d",&a,&b);
    for(int x=1;x<=a;++x)scanf("%d",&c[x]);
    sort(c+1,c+a+1);//sort从小到大排
    dfs(1,b);//打暴力
    printf("%d",ans);
    return 0;
}