# 2017多校六 1008题 hdu 6103 Kirinriki 尺取法

cost 的定义为 sigma(i = 0 ~ n - 1) (abs(A[i] - B[n - 1 - i])).

Code:

``````#include bits/stdc++.h
#define maxn 5010
char s[maxn];
int n;
inline int max(int a, int b) { return a  b ? a : b; }
int count1(char* s) {
int len = strlen(s), ret = 0;
for (int i = 0; i  len - 1; ++i) {
int l1, r1, l2, r2, sum = 0, ans = 0;
l1 = r1 = i, l2 = r2 = i + 1;
while (true) {
bool flag = false;
while (l1 = 0  r2  len) {
sum += abs(s[l1] - s[r2]);
if (sum  n) break;
--l1, ++r2;
}
ans = max(ans, r1 - l1);
if (sum = n) break;
sum -= abs(s[r1--] - s[l2++]);
--l1, ++r2;
}
ret = max(ret, ans);
}
return ret;
}
int count2(char* s) {
int len = strlen(s), ret = 0;
for (int i = 1; i  len - 1; ++i) {
int l1, r1, l2, r2, sum = 0, ans = 0;
l1 = r1 = i - 1, l2 = r2 = i + 1;
while (true) {
bool flag = false;
while (l1 = 0  r2  len) {
sum += abs(s[l1] - s[r2]);
if (sum  n) break;
--l1, ++r2;
}
ans = max(ans, r1 - l1);
if (sum = n) break;
sum -= abs(s[r1--] - s[l2++]);
--l1, ++r2;
}
ret = max(ret, ans);
}
return ret;
}
void work() {
scanf("%d%s", n, s);
printf("%d\n", max(count1(s), count2(s)));
}
int main() {
int T;
scanf("%d", T);
while (T--) work();
return 0;
}
``````

• 04:47
• 03:31
• 01:09
• 02:13
• 01:07:52
• 00:46