[ACM] FZU 2086 餐厅点餐 (枚举)

roblem Description

Jack近期喜欢到学校餐厅吃饭。好吃干净还廉价。

在学校餐厅。有a种汤,b种饭。c种面条,d种荤菜,e种素菜。

为了保证膳食搭配,Jack每顿饭都会点1~2样荤菜,1~2样素菜(不反复)。同一时候,在Jack心情好的时候,会点一样饭,再配上一种汤。在心情不好的时候,就仅仅吃一种面条。

由于经济有限,Jack每次点餐的总价在min~max之间。

Jack想知道,总共同拥有多少种不同的点餐方案。

 Input

输入数据第一行包括一个整数T,表示測试数据的组数。对于每组測试数据:

第一行为整数a,b,c,d,e(0<a,b,c,d,e<=10)

第二行为a个大于零的整数,表示a种汤的价格

第三行为b个大于零的整数,表示b种饭的价格

第四行为c个大于零的整数,表示c种面条的价格

第五行为d个大于零的整数,表示d种荤菜的价格

第六行为e个大于零的整数,表示e种素菜的价格

第七行为两个整数min max,表示每次点餐的价格范围

 Output

对于每组測试数据。输出一行,包括一个整数。表示点餐方案数。

 Sample Input

12 2 2 2 22 33 15 21 43 65 8

 Sample Output

3

 Source

福州大学第九届程序设计竞赛

解题思路:

又是由于没看清题意。

。。

点餐不光要有荤有素,还必须有饭汤或面条。

代码:

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <iomanip>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <ctype.h>
using namespace std;
int tang,fan,mian,hun,su;
int Tang[11],Fan[11],Mian[11],Hun[11],Su[11];
int Min,Max;

bool ok(int n)
{
    if(n>=Min&&n<=Max)
        return true;
    return false;
}
int p[100000];

int main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>tang>>fan>>mian>>hun>>su;
        for(int i=1;i<=tang;i++)
            scanf("%d",&Tang[i]);
        for(int i=1;i<=fan;i++)
            scanf("%d",&Fan[i]);
        for(int i=1;i<=mian;i++)
            scanf("%d",&Mian[i]);
        for(int i=1;i<=hun;i++)
            scanf("%d",&Hun[i]);
        for(int i=1;i<=su;i++)
            scanf("%d",&Su[i]);
        cin>>Min>>Max;
        int cnt=0;
        int len=0;

        for(int i=1;i<=hun;i++)//一荤一素
        {
            if(Hun[i]>=Max)
                continue;
            for(int j=1;j<=su;j++)
            {
                if(Su[j]>=Max)
                continue;
                int temp=Hun[i]+Su[j];
                if(temp<Max)
                    p[++len]=temp;
            }
        }
        for(int i=1;i<=hun;i++)//一荤两素
        {
            if(Hun[i]>=Max)
                continue;
            for(int j=1;j<=su;j++)
            {
                if(Su[j]>=Max)
                    continue;
                for(int k=j+1;k<=su;k++)
                {
                    if(Su[k]>=Max)
                        continue;
                    int temp=Hun[i]+Su[j]+Su[k];
                    if(temp<Max)
                        p[++len]=temp;
                }
            }
        }
        for(int i=1;i<=hun;i++)//两荤一素
        {
                if(Hun[i]>=Max)
                continue;
                for(int j=i+1;j<=hun;j++)
                {
                    if(Hun[j]>=Max)
                        continue;
                    for(int k=1;k<=su;k++)
                    {
                        if(Su[k]>=Max)
                            continue;
                        int temp=Hun[i]+Hun[j]+Su[k];
                        if(temp<Max)
                            p[++len]=temp;
                    }
                }
        }

        for(int i=1;i<=hun;i++)//两荤两素
        {
            if(Hun[i]>=Max)
                continue;
            for(int j=i+1;j<=hun;j++)
            {
                if(Hun[j]>=Max)
                    continue;
                for(int s=1;s<=su;s++)
                {
                    if(Su[s]>=Max)
                        continue;
                    for(int q=s+1;q<=su;q++)
                    {
                        if(Su[q]>=Max)
                            continue;
                        int temp=Hun[i]+Hun[j]+Su[s]+Su[q];
                        if(temp<Max)
                            p[++len]=temp;
                    }
                }
            }
        }
        for(int i=1;i<=len;i++)
        {
            for(int fan1=1;fan1<=fan;fan1++)
            {
                int p1=p[i];
                p1+=Fan[fan1];
                int d=p1;
                for(int tang1=1;tang1<=tang;tang1++)
                {
                    p1=d;//注意这一句
                    p1+=Tang[tang1];
                    if(ok(p1))
                        cnt++;
                }
            }
            for(int mian1=1;mian1<=mian;mian1++)
            {
                int p2=p[i];
                p2+=Mian[mian1];
                if(ok(p2))
                    cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}


 

原文地址:https://www.cnblogs.com/tlnshuju/p/6780092.html