题解 meeting

wasa855 · 2018-07-07 20:29:09 · 个人记录

看到数据范围m、n<=6，明显，这是一道爆搜题，注意：每个人可以不参加项目、参加1个项目，参加2个项目。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
struct person
{
    int talent[10];
    bool used[10];
    int sp;
};
person p[10];
struct Meet
{
    int per;
};
Meet meet[10];
int maxn=0;
int m,n;
void dfs(int per,int now)
{
    if(now>maxn)
    {
        maxn=now;
    }
    if(per==m+1)
    {
        return ;
    }//边界条件
    dfs(per+1,now);
    p[per].sp++;
    for(int i=1;i<=n;i++)
    {
        if(meet[i].per==2)
        {
            continue;
        }
        meet[i].per++;
        now+=p[per].talent[i];
        dfs(per+1,now);//参加一个项目
        meet[i].per--;
        now-=p[per].talent[i];
    }
    p[per].sp=2;
    for(int i=1;i<=n;i++)
    {
        if(meet[i].per==2)
        {
            continue;
        }
        meet[i].per++;
        now+=p[per].talent[i];
        for(int j=i+1;j<=n;j++)
        {
            if(meet[j].per==2)
            {
                continue;
            }
            meet[j].per++;
            now+=p[per].talent[j];
            dfs(per+1,now);//参加两个项目
            meet[j].per--;
            now-=p[per].talent[j];
        }
        meet[i].per--;
        now-=p[per].talent[i];
    }
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&p[i].talent[j]);
        }
    }
    dfs(1,0);
    cout<<maxn<<endl;
    return 0;
}