首页 > 其他 > 详细

洛谷P6248 准备战斗,选择你的英雄

时间:2020-03-29 13:35:50      阅读:55      评论:0      收藏:0      [点我收藏+]

0、自闭

这题比赛完后看题解突然感觉真的简单TAT

1、题意

\(n\)个字符串,每个字符串\(s\)都有一个权值\(a[i]\),你要在其中选\(6\)个字符串,还有m个组合,每个组合是两个字符串,如果第\(m[i]\)个组合中,两个字符串都被选中了,那么还可以额外加权值\(b[i]\),求选\(6\)个字符串的最大权值。
\(n≤30\)\(m≤30\),字符串长度\(≤100\)\(a[i],b[i]≤100\)
\(40%\)的数据,\(m=0\)

2、思路

前四个点很好过,从大到小排序,取前六个,加起来输出即可。
对于全部数据点,可以看出,就是在\(31\)个数里面选\(6\)个数,使用DFS写全排列即可。
再加入\(m\)个组合,每次搜出一组解后\(check()\)判断一下是否组成其中的每个组合,如果组成就把那个组合额外的权值加上去。
然后对于每一组解求max,输出。
\(f[i]\)表示第\(i\)个英雄的位置,并使用\(map\)函数,把字符串(名字)全部转换成数字。
然后就和全排列模板一样写就行了。

3、code:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
map <string,int > mapp ;
const int M=10;
const int N=55;
int n,m,x[N],y[N],a[N],f[M],t[N],ans=-1;
void check()
{
	int temp=0;
	for(int i=1;i<=6;i++)
	{
		temp+=a[f[i]];//注意是a[f[i]],因为是位置
	}
	for(int i=1;i<=m;i++)
	{
		bool f1,f2;
		f1=f2=0;
		for(int j=1;j<=6;j++)
		{
			if(f[j]==x[i])
			{
				f1=true;
			}
			else if(f[j]==y[i])
			{
				f2=true;
			}
		}
		if(f1!=0&&f2!=0)//如果两个都有,表示此组合配对,加上额外权值
		{
			temp+=t[i];
		}
	}
	ans=max(temp,ans);//每次取max
}
void dfs(int k)
{
	if(k>6)//如果搜到一组解,开始判断
	{
		check();
		return;
	}
	else
	{
		for(int i=f[k-1]+1;i<=n;i++)//因为后面的一定要比前面的大(显而易见),无需搜完
		{
			f[k]=i;
			dfs(k+1);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s>>a[i];
		mapp[s]=i;
	}
	for(int i=1;i<=m;i++)
	{
		string s1,s2;
		cin>>s1>>s2>>t[i];
		x[i]=mapp[s1];
		y[i]=mapp[s2];//用map函数,字符串转数字
	}
	dfs(1);
	cout<<ans;
    return 0;
}

洛谷P6248 准备战斗,选择你的英雄

原文:https://www.cnblogs.com/pjxpjx/p/12591083.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!