SDUT 2860-生日Party（BFS）

生日Party

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描写叙述

Sherlock的生日即将来临，Sherlock打算邀请几个好友来參加自己的生日Party。为了让Party尽可能的happy，经过Sherlock的调查发现每一个好友都有一个happy值。并且Sherlock的好友之间也存在复杂的关系，当好友中的某两个人同一时候出如今Party的时候，会产生一个额外的happy值，幸亏Sherlock好友不算多，Sherlock打算邀请部分或所有好友（也可能一个都不邀请），好让Party的happy值最高

输入

有多组数据，首先一个整数T表示所给数据的组数。每组数据第一行一个整数n（0<n<=15），表示Sherlock的好友人数。第二行n个整数依次表示每一个好友假设来參加Party将会产生的happy值，接下来n行，每行n个整数，第i行的第j个整数表示当第i个好友和第j个好友同一时候參加party是产生的额外happy值 注意，所给数据中的happy值的范围为(-100~100)

输出

每组数据输出一行，Sherlock的Party最高的happy值

演示样例输入

4 2 1 2 0 -2 -2 0 3 -1 -1 0 0 1 1 1 0 1 1 1 0 3 1 1 1 0 -1 -1 -1 0 -1 -1 -1 0 3 -1 -1 -1 0 -2 -2 -2 0 -2 -2 -2 0

演示样例输出

2 1 1 0

之前一直在往dp方面想，结果一直推不出状态转移方程。。（sad 我dp就是个渣啊）并且mjj也说这是dp 防ak的 后来突然看到scf用暴搜过的！好吧我承认我也想过但前天才学的bfs之前也敲不出来，话说回来这题暴搜的思路也是非常灵异的，对于第i个朋友，有两种状态，所以搜完一轮复杂度为O(2^15) 不须要标记数组，硬搜救能够了
 #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> #include <queue> using namespace std; typedef struct node {int a[20],ans,x,top;//a数组里面放參加party的朋友的编号 }; int ma[20][20]; int fri[20],Max,n; void bfs() {node t,v;queue <node> Q;t.top=0;t.ans=0;t.x=-1;Q.push(t);while(!Q.empty()){v=Q.front();Q.pop();if(v.x==n-1)//每选完一轮更新一下最大值{if(Max<v.ans)Max=v.ans;continue;}//两个搜索方向，要么选此人，要么不选t.x=v.x+1;//不选第i个人t.ans=v.ans;t.top=v.top;for(int i=0;i<v.top;i++)t.a[i]=v.a[i];Q.push(t);//选第i个人t.top=v.top+1;t.a[v.top]=t.x;t.ans=v.ans+fri[t.x];for(int i=0;i<v.top;i++)t.ans+=ma[t.a[i]][t.x];Q.push(t);} } int main() {int T,i,j;cin>>T;while(T--){cin>>n;for(i=0;i<n;i++)cin>>fri[i];for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>ma[i][j];Max=-1;bfs();if(Max<0)cout<<"0"<<endl;elsecout<<Max<<endl;}return 0; }

转载于:https://www.cnblogs.com/blfshiye/p/4290000.html

总结

以上是生活随笔为你收集整理的SDUT 2860-生日Party（BFS）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。