文档章节

[HDU2296]Ring

o
 osc_zfz30hgc
发布于 2018/01/26 12:34
字数 816
阅读 17
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

vjudge ###Description For the hope of a forever love, Steven is planning to send a ring to Jane with a romantic string engraved on. The string's length should not exceed N. The careful Steven knows Jane so deeply that he knows her favorite words, such as "love", "forever". Also, he knows the value of each word. The higher value a word has the more joy Jane will get when see it. The weight of a word is defined as its appeared times in the romantic string multiply by its value, while the weight of the romantic string is defined as the sum of all words' weight. You should output the string making its weight maximal. ###Input The input consists of several test cases. The first line of input consists of an integer T, indicating the number of test cases. Each test case starts with a line consisting of two integers: N, M, indicating the string's length and the number of Jane's favorite words. Each of the following M lines consists of a favorite word Si. The last line of each test case consists of M integers, while the i-th number indicates the value of Si. Technical Specification

1. T ≤ 15
2. 0 < N ≤ 50, 0 < M ≤ 100.
3. The length of each word is less than 11 and bigger than 0.
4. 1 ≤ Hi ≤ 100.
5. All the words in the input are different.
6. All the words just consist of 'a' - 'z'.

###Output For each test case, output the string to engrave on a single line. If there's more than one possible answer, first output the shortest one. If there are still multiple solutions, output the smallest in lexicographically order. The answer may be an empty string. ###Sample Input

2
7 2
love
ever
5 5
5 1
ab
5

###Sample Output

lovever
abab

简单翻译一下:给出m个模式串(m≤100),每个模式串有一个权值。先要求构造一个长度不大于n(n≤50)的串使其包含的子模式串的权值和最大。若存在多解,则要求输出长度最小的,若仍存在多解则要求输出字典序最小的。 #sol DP出最大权值应该不难吧 要求字典序最小其实也很好办。开一个string记录路径就行了(string自带比较字典序)。 ##code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1500;
int T,n,m,tot,ch[26][N],fail[N],cnt[N],node[101],dp[55][N];
string path[55][N];
char s[N];
queue<int>Q;
void Insert(int k)
{
	cin>>s;int l=strlen(s),x=0;
	for (int i=0;i<l;i++)
	{
		if (!ch[s[i]-'a'][x]) ch[s[i]-'a'][x]=++tot;
		x=ch[s[i]-'a'][x];
	}
	node[k]=x;
}
void Get_Fail()
{
	for (int i=0;i<26;i++) if (ch[i][0]) Q.push(ch[i][0]);
	while (!Q.empty())
	{
		int u=Q.front();Q.pop();
		for (int i=0;i<26;i++)
			if (ch[i][u]) fail[ch[i][u]]=ch[i][fail[u]],Q.push(ch[i][u]);
			else ch[i][u]=ch[i][fail[u]];
		cnt[u]+=cnt[fail[u]];
	}
}
void DP()
{
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0;path[0][0]="";
	for (int i=0;i<n;i++)
		for (int j=0;j<=tot;j++)
			if (dp[i][j]!=-1)
				for (int k=0;k<26;k++)
				{
					int u=ch[k][j];
					if (dp[i][j]+cnt[u]>dp[i+1][u])
					{
						dp[i+1][u]=dp[i][j]+cnt[u];
						path[i+1][u]=path[i][j]+(char)(k+'a');
					}
					else if (dp[i][j]+cnt[u]==dp[i+1][u])
					{
						string str=path[i][j]+(char)(k+'a');
						if (str<path[i+1][u]) path[i+1][u]=str;
					}
				}
}
int main()
{
	cin>>T;
	while (T--)
	{
		cin>>n>>m;
		for (int i=0;i<=tot;i++)
		{
			fail[i]=cnt[i]=0;
			for (int j=0;j<26;j++) ch[j][i]=0;
		}
		tot=0;
		for (int i=1;i<=m;i++) Insert(i);
		for (int i=1,v;i<=m;i++) cin>>v,cnt[node[i]]+=v;
		Get_Fail();
		DP();
		string str="";int ans=0,maxx=0;
		for (int i=1;i<=n;i++)
			for (int j=0;j<=tot;j++)
				maxx=max(maxx,dp[i][j]);
		for (int i=1;i<=n;i++)
		{
			for (int j=0;j<=tot;j++)
				if (dp[i][j]>ans||(dp[i][j]==ans&&path[i][j]<str))
					ans=dp[i][j],str=path[i][j];
			if (ans==maxx) break;
		}
		cout<<str<<endl;
	}
	return 0;
}
o
粉丝 0
博文 499
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
ntop 2016 路线图

ntop 2016 路线图 2015年是一个充满活力的年份,我们得以完善工具,为社区提供更好的服务。 2016年计划如下: 100 Gbit 正如在2015年我们已经在PF_RING 中为40 Gbit提供了支持,2016年将为100...

RiboseYim
2016/02/08
795
0
【转载】自制4412底板自动进入SD卡更新模块

转载自迅为论坛:http://www.topeetboard.com 参考平台:迅为iTOP-4412开发板 问题如下:在自制的底板上,当SD卡插在板子上开机时,会自动进入Updating模式,如果SD卡有sdupdate文件夹并且有...

歌之王子殿下
2017/02/15
202
0
高性能的网络应用的C++库--Herm

Herm是一套快速开发高性能的网络应用的C++库。比如开发网络游戏、即时通信、流媒体、文件下载、P2P等基于TCP/IP网络应用。(此项目已经不存在) Herm包括三个组件: (1)Utilities 最基础的...

匿名
2010/10/31
1W
0
分布式JSON对等协议--TeleHash

TeleHash 是一个新的用来实时和去中心化的JSON交互协议,可让应用在网络的边界直接进行连接。受益于 TeleHash,应用程序之间可高效的进行路由和分发小的数据。 示例: // basic Telex with ...

匿名
2010/05/22
1.3K
0
Ajax的源码编辑器--Ymacs

Ymacs是一个为程序员提供的可扩展的AJAX文本编辑器。它与Emacs类似:它支持多个缓冲区,分割帧,动态完成,多个按键,和Emacs一样撤消队列和kill ring。当然,Emacs的一样的,所有的键绑定。...

匿名
2009/12/15
1.2K
0

没有更多内容

加载失败,请刷新页面

加载更多

禁用win10无用服务,提高Win10系统游戏性能!

长按二维码关注网络杀手 分享有态度的最好应用 分享干货满的学习教程 网络杀手 公众号的发展离不开大家的支持,非常感谢各位的关注!小编以后会继续努力加油,为大家分享更多更好的教程和应用...

whiteshds
今天
5
0
聊聊dubbo-go的forkingCluster

序 本文主要研究一下dubbo-go的forkingCluster forkingCluster dubbo-go-v1.4.2/cluster/cluster_impl/forking_cluster.go type forkingCluster struct{}const forking = "forking"func......

go4it
今天
13
0
如何在Vim中进行不区分大小写的搜索 - How to do case insensitive search in Vim

问题: I'd like to search for an upper case word, for example COPYRIGHT in a file. 我想搜索大写单词,例如文件中的COPYRIGHT。 I tried performing a search like: 我尝试过执行搜索:......

富含淀粉
今天
17
0
Flutter+FaaS一体化任务编排的思考与设计

简介: 闲鱼flutter faas一体化提升研发体验+研发质量 作者:闲鱼技术-古风 Flutter+Serverless三端一体研发架构,客户端不仅仅是编写双端的代码,而是扩展了客户端的工作边界,形成完整的业...

一肥仔
今天
21
0
lodash和下划线之间的差异[关闭] - Differences between lodash and underscore [closed]

问题: Why would someone prefer either the lodash.js or underscore.js utility library over the other? 为什么有人更喜欢lodash.js或underscore.js实用程序库而不是另一个? Lodash see......

fyin1314
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部