首页 > 代码库 > HDU 6103 Kirinriki（尺取法）
HDU 6103 Kirinriki（尺取法）
http://acm.hdu.edu.cn/showproblem.php?pid=6103
题意：
给出一个字符串，在其中找两串互不重叠的子串，计算它们之间的dis值
，要求dis值小于等于m，求能选的子串的最大长度。
思路：
由于这两个子串是互不重叠的，那么这两个子串之间的间隔可以是奇数也可以是偶数，针对这两种情况我们枚举中心点，然后尺取法处理，具体看代码就懂了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,ll> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn=5000+5;17 18 int n, m;19 int cnt;20 int ans;21 char s[maxn];22 int tmp[maxn];23 24 void check()25 {26 int l=0,r=0;27 int dis=0;28 while(r<cnt)29 {30 dis+=tmp[++r];31 while(dis>m) dis-=tmp[++l];32 ans=max(ans,r-l);33 }34 }35 36 int main()37 {38 //freopen("in.txt","r",stdin);39 int T;40 scanf("%d",&T);41 while(T--)42 {43 scanf("%d",&m);44 scanf("%s",s+1);45 n=strlen(s+1);46 47 ans=0;48 for(int i=1;i<=n;i++) //中间相隔奇数49 {50 int l=i-1,r=i+1;51 cnt=0;52 while(l>0 && r<=n) {tmp[++cnt]=abs(s[l]-s[r]);l--;r++;}53 check();54 }55 56 for(int i=1;i<=n;i++) //中间相隔偶数57 {58 int l=i,r=i+1;59 cnt=0;60 while(l>0 && r<=n) {tmp[++cnt]=abs(s[l]-s[r]);l--;r++;}61 check();62 }63 64 printf("%d\n",ans);65 }66 return 0;67 }
HDU 6103 Kirinriki（尺取法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。