Codeforces Round #622 (Div. 2) A. Fast Food Restaurant（全排列，DFS）

Codeforces Round #622 (Div. 2) A. Fast Food Restaurant

题意：

你是餐馆老板，虽然只会做三道菜，上菜时还有个怪癖：一位客人至少上一道菜，且一种菜最多上一次，所有客人菜单不能相同。给出三种菜的数量，问最多能接收多少客人。

思路：

一人一道 → 一人两道 → 一人三道。

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int t;cin>>t;

    while(t--){

        int a[3];for(int &i:a) cin>>i;

        int ans=0;

        for(int i=0;i<3;i++)

            if(a[i]) --a[i],++ans;

        sort(a,a+3,greater<int>());

        for(int i=0;i<3;i++)

            if(a[i]&&a[(i+1)%3])

                --a[i],--a[(i+1)%3],++ans;

        if(a[0]&&a[1]&&a[2]) ++ans;

        cout<<ans<<endl;

    }

    return 0;

}

拓展：

你疫情在家闲的没事干多学做了几道菜。

#include <bits/stdc++.h>

using namespace std;

const int M=3;//会做几种菜

int a[M],ans;

vector<int> index;

bool ok(){

    for(int &i:index)

        if(a[i]==0) return false;

    return true;

}

void dfs(int start,int dep,int max_dep){

    if(dep>max_dep){

        if(ok()){

            for(int &i:index)  --a[i];

            ++ans;

        }

        return;

    }

    for(int i=start;i<M;i++)

        if(a[i]){

            index.push_back(i);

            dfs(i+1,dep+1,max_dep);

            index.pop_back();

        }

}

void solve(){

    for(int &i:a) cin>>i;

    sort(a,a+M,greater<int>());

    ans=0;

    for(int i=0;i<M;i++)

        dfs(0,0,i);

    cout<<ans<<endl;

}

int main()

{

    int t;cin>>t;

    while(t--)

        solve();

    return 0;

}

巴特西

Codeforces Round #622 (Div. 2) A. Fast Food Restaurant（全排列，DFS）

题意：

思路：

拓展：

最新文章

热门文章