## [HDU2296]Ring 转

o
osc_zfz30hgc

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
``````

``````#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

### osc_zfz30hgc

ntop 2016 路线图

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

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

2017/02/15
202
0

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

2010/10/31
1W
0

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

whiteshds

5
0

go4it

13
0

17
0
Flutter+FaaS一体化任务编排的思考与设计

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

fyin1314

14
0