2010辽宁省赛F(字典树,动态规划)
2024-10-20 18:54:13
#include<bits/stdc++.h>
using namespace std;
int n,x;
char s[10010];
char a[31010];
int val[100010];
int ch[100010][30];
int dp[100010];
int main()
{
while(~scanf("%d",&n))
{
scanf("%s",s+1);
int len=strlen(s+1);
memset(ch[0],0,sizeof(ch[0]));
int cnt=0;//记录编号
for(int i=1;i<=n;i++)
{
int u=0;//父节点,0为根节点
scanf("%s%d",a,&x);
for(int j=0;j<strlen(a);j++)
{
if(!ch[u][a[j]-'a'])//字典树中该位置已存在该字母
{
ch[u][a[j]-'a']=++cnt;
memset(ch[cnt],0,sizeof(ch[cnt]));
val[cnt]=0;
using namespace std;
int n,x;
char s[10010];
char a[31010];
int val[100010];
int ch[100010][30];
int dp[100010];
int main()
{
while(~scanf("%d",&n))
{
scanf("%s",s+1);
int len=strlen(s+1);
memset(ch[0],0,sizeof(ch[0]));
int cnt=0;//记录编号
for(int i=1;i<=n;i++)
{
int u=0;//父节点,0为根节点
scanf("%s%d",a,&x);
for(int j=0;j<strlen(a);j++)
{
if(!ch[u][a[j]-'a'])//字典树中该位置已存在该字母
{
ch[u][a[j]-'a']=++cnt;
memset(ch[cnt],0,sizeof(ch[cnt]));
val[cnt]=0;
}
u=ch[u][a[j]-'a'];
}
val[u]=max(val[u],x);//u为结尾结点的编号,val[u]表示该串的权重
}
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=len;i++)
{
int u=0;
if(!dp[i-1])
continue;
for(int j=i;j<=i+30&&j<=len;j++)
{
if(ch[u][s[j]-'a'])
{
u=ch[u][s[j]-'a'];
if(val[u])//如果有以u结尾的字符串,检验它的权重加上i结束的字符串的权重是否比原来更大
dp[j]=max(dp[j],dp[i-1]+val[u]);
}
else
break;
}
}
u=ch[u][a[j]-'a'];
}
val[u]=max(val[u],x);//u为结尾结点的编号,val[u]表示该串的权重
}
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=len;i++)
{
int u=0;
if(!dp[i-1])
continue;
for(int j=i;j<=i+30&&j<=len;j++)
{
if(ch[u][s[j]-'a'])
{
u=ch[u][s[j]-'a'];
if(val[u])//如果有以u结尾的字符串,检验它的权重加上i结束的字符串的权重是否比原来更大
dp[j]=max(dp[j],dp[i-1]+val[u]);
}
else
break;
}
}
//模拟从开始到完成字符串加入进行匹配的过程
printf("%d\n",dp[len]-1);
}
return 0;
}
}
return 0;
}
//字典树是一种以空间换时间的数据结构,在ch数组中,第一维表示父节点,第二维表示兄弟节点。每个节点挂一个链表,把它后面的节点连起来,对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数。
最新文章
- 我的MYSQL学习心得(二) 数据类型宽度
- 【CSS】css自定义字体
- 【读书笔记】iOS-GCD-GCD与perfomSelector系方法比较
- 我的 GitHub 100 连击
- [codeforces 519E]E. A and B and Lecture Rooms(树上倍增)
- 设计算法,求AB两个整数集合的交集
- Python Counter()计数工具
- dmesg 程序崩溃调试2
- 跟着Android学设计模式:代理(proxy)
- Effective C++ 第二版 5)new和delete形式 6) 析构函数里的delete
- C# VS 面向对象基础(一)
- date tod = boost::gregorian::day_clock::local_day(); //当前日期
- 【阿里云API】 阿里云API调用的若干说明
- 使用eclipse初步学习vue.js基础==》v-for的使用 ②
- C# 连接Oracle时报错的问题
- GATT服务搜索流程(一)
- 新建asp.net core项目
- Misha and Palindrome Degree CodeForces - 501E (回文串计数)
- EntityFramework Core 学习扫盲
- C#编程(十九)----------部分类