大致题意:
要把n个字符串首尾相连成若干个环,如果把s1接到s2的后面可以得到一定的收获值,这个值等于s2的逆序 和s1的最长相同前缀的长度。求总收获值最大是多少。
大致思路:
看完题就感觉是KM二分图最大全匹配,匹配部分思路和hdu1853类似。感觉字符串部分的复杂度过高,以为有什么牛逼的算法,迟迟不敢下手敲,看了别人题解才发现暴力就行了。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int nMax=204;
const int mMax=1005;
const int inf=1<<29;
int map[nMax][nMax];
int lx[nMax],ly[nMax];
int mapch[nMax];
int stack[nMax];
bool sy[nMax],sx[nMax];
int n,m,e,cnt;
int find (int u){
int v,t;
sx[u]=1;
for(v=1;v<=m;v++){
if(sy[v]) continue;
t=lx[u]+ly[v]-map[u][v];
if(t==0){
sy[v]=1;
if(mapch[v]==-1||find(mapch[v])){
mapch[v]=u;
return 1;
}
}
else if(t<stack[v]) stack[v]=t;
}
return 0;
}
int KM(){
int i,j,k,d,sum=0;
cnt=0;
for(i=1;i<=m;i++)
ly[i]=0;
memset(mapch,-1,sizeof(mapch));
for(i=1;i<=n;i++){
lx[i]=-inf;
for(j=1;j<=m;j++)
if(map[i][j]>lx[i])
lx[i]=map[i][j];
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
stack[j]=inf;
while(1){
for(k=1;k<=m;k++) sy[k]=0;
for(k=1;k<=n;k++) sx[k]=0;
if(find(i)) break;
d=inf;
for(k=1;k<=m;k++)
if(!sy[k]&&stack[k]<d)
d=stack[k];
for(k=1;k<=n;k++)
if(sx[k]) lx[k]-=d;
for(k=1;k<=m;k++)
if(sy[k]) ly[k]+=d;
else stack[k]-=d;
}
}
for(i=1;i<=m;i++)
if(mapch[i]!=-1&&map[mapch[i]][i]!=-inf){
sum+=map[mapch[i]][i];
}
return sum;
}
char str[nMax][1003];
int maxpre(int a,int b){
int i,j;
int ans=0;
int la=strlen(str[a]);
int lb=strlen(str[b]);
for(i=0,j=lb-1;;){
if(i<la&&j>=0&&str[a][i]==str[b][j]){
i++;
j--;
ans++;
}
else break;
}
return ans;
}
int main(){
int i,j;
while(scanf("%d",&n)!=EOF){
m=n;
memset(map,0,sizeof(map));
for(i=1;i<=n;i++){
scanf("%s",str[i]);
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(i==j)continue;
map[i][j]=maxpre(i,j);
}
}
printf("%d\n",KM());
}
return 0;
}
分享到:
相关推荐
HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户更好地组织和筛选题目,以便针对不同主题进行...
【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...
每个源代码文件通常会包含完整的算法实现、注释以及必要的输入输出处理,以便在HDOJ平台上进行测试和提交。 通过深入研究这些Java源代码,开发者可以学习到以下关键知识点: 1. **基本语法**:Java的变量声明、...
1. **学习算法与数据结构**:HDOJ包含了丰富的算法题目,如排序、搜索、图论、动态规划、贪心算法等,是学习和提升算法能力的理想平台。通过解决这些题目,你可以深入理解各种算法的实际应用和性能分析。 2. **提高...
【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵的资源库,供程序员学习、参考和练习算法。HDOJ是许多编程爱好者和竞赛选手熟悉的一个平台,它提供了各种难度级别的编程题目,涵盖了...
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
“hdoj 2013 多校训练2标程+解题报告”这个标题指的是2013年举行的一场由hdoj(HDU Online Judge,即杭州电子科技大学在线评测系统)组织的多校联合编程训练活动的第二阶段。其中,“标程”是指官方提供的正确解答...
在计算机科学领域,特别是编程竞赛和算法设计中,ACM(International Collegiate Programming Contest,国际大学生程序设计竞赛)是一项极具挑战性的活动。这个比赛要求参赛团队在短时间内解决一系列复杂的算法问题...
这些文件是针对“hdoj”(HDU Online Judge)在线编程竞赛平台的解题代码,涵盖了题目编号从1000到1050的若干题目。HDU Online Judge是一个用于训练和测试编程技能的系统,用户可以提交代码解决各种算法问题,并获取...
_algorithm_stepped8pp”指的是一个压缩文件,其中包含的主要是与“HDOJ”(Happy Dog Online Judge)平台相关的代码,特别是作者自己的解决算法。"Mine!"可能表示这些代码是个人的作品,而"stepped8pp"可能是某种...
HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
【标题】"HDOJ2019(杭电多校第一场的数据与标程).zip" 提供的是2019年杭州电子科技大学(HDOJ,杭电在线评测系统)多校联合竞赛的第一场的比赛数据和官方参考解题代码,即“标程”。这类资源对于参加ACM/ICPC...
leetcode和hdoj 简介 主要用来记录算法刷题记录和一些模板 文件结构 leetcode 存放leetcode题目和周赛 atcoder 用于存放参与和vp的atcoder比赛 codeforces 用于存放参与和vp的cf比赛,比赛文件夹以比赛序号和div描述...