Kirinriki
time limit per test 1 second memory limit per test 256 megabytes
We define the distance of two strings A and B with same length n is
disA,B=∑i=0n−1|Ai−Bn−1−i|
The difference between the two characters is defined as the difference in ASCII.
You should find the maximum length of two non-overlapping substrings in given string S, and the distance between them are less then or equal to m.

传送门:HDU6103

Input

The first line of the input gives the number of test cases T; T test cases follow. Each case begins with one line with one integers m : the limit distance of substring. Then a string S follow. Limits T≤100 0≤m≤5000 Each character in the string is lowercase letter, 2≤|S|≤5000 ∑|S|≤20000

Output

For each test case output one interge denotes the answer : the maximum length of the substring.

Sample Input

1
2
3
1
5
abcdefedcb

Sample Output

1
5

题解

要有灵性= = 这题的简化版本就是一段数列找和小于m的最长长度 因为长度相同的一定是根据某个点对称的 所以可以枚举中心点然后尺取 还有一个要注意的地方是这个中心点有两种情况比如AABB这样对称的话枚举中心点是第一段的末尾(可以理解为中心点坐标在1.5) 而AACBB中心点在他们之间且是整数点(可以理解为中心点坐标为2) 这是两种不同的情况注意不要漏了
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
while(sc.hasNext()){
int m=sc.nextInt();
String ss=sc.next();
int n=ss.length();
int[]shu=new int[n];
for(int i=0;i<n;i++){
shu[i]=(int)ss.charAt(i);
}
int cen=0;
int max=0;
for(int i=0;i<n;i++){ //枚举中心点是第一段末尾
int s1=i;
int e1=i;
int s2=i+1;
int e2=i+1;
int sum=0;
while(true){
while(e2<n&&s1>=0&&sum<=m){
max=Math.max(max, e2-s2);
sum+=Math.abs(shu[e2]-shu[s1]);
e2++;
s1--;
}
if(sum<=m){
max=Math.max(max, e2-s2);
break;
}
sum-=Math.abs(shu[e1]-shu[s2]);
s2++;
e1--;
}
}
for(int i=0;i<n;i++){ //枚举中心点是两段之间的整点
int s1=i-1;
int e1=i-1;
int s2=i+1;
int e2=i+1;
int sum=0;
while(true){
while(e2<n&&s1>=0&&sum<=m){
max=Math.max(max, e2-s2);
sum+=Math.abs(shu[e2]-shu[s1]);
e2++;
s1--;
}
if(sum<=m){
max=Math.max(max, e2-s2);
break;
}
sum-=Math.abs(shu[e1]-shu[s2]);
s2++;
e1--;
}
}
pw.println(max);
pw.flush();
}

}
}