题解 P1164 【小A点菜】

· · 题解

3.10更 改了一个错字

因为这题放在了动态规划的背包问题里，所以很明显是一个01背包

但是，看完数据范围之后，感觉搜索也能过 其实是不会写动规

逛完题解后发现大佬们都是dp或dfs，本蒟蒻就写个bfs献丑了

因为有n<=100种菜品，每种菜都有点或不点两种选择，所以最多会有2^100种情况， 这么长的队列很明显是写不了 但幸亏uim很穷 很多情况下菜还没点几个就没钱了，然后可以直接判断这种情况是否正确，往下的菜单就不必看了，所以实际入队的情况不会有这么多，c++支持的最大一维数组应该是够用的，没想的真的够用

#include<iostream>
#include<cstdio>
using namespace std;
int q[9999999];//队列 也许可以更小一些，没有尝试
int tot[9999999];
int main(){
    int n,m,ans=0;
    tot[1]=1;
    cin>>n>>m;
    q[0]=m;
    int h=0,t=1;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        for(int j=1;j<=tot[i];j++){//把入队的几个全部询问一边
            q[t++]=q[h];tot[i+1]++;//入队和记录入队个数
            if(q[h]-x==0){
                ans++;
            }
            if(q[h]-x>0){
                q[t++]=q[h]-x;tot[i+1]++;//入队和记录入队个数
            }
            h++;
        }
    }
    cout<<ans;
    return 0;
}

我才不会说第一次交的时候数组开太大直接RE了