POJ 3276 [Face The Right Way] 题解

题目大意

n头牛排成一行,有的牛面朝前,有的牛面朝后,每一次操作可以使连续的K头牛改变方向;求一个K,使得操作次数最少。输出K以及最少的操作次数。当有多个K满足条件时,输出最小的K。

题目分析

对一个区间来说,多次进行反转操作是没有意义的;另外反转的顺序对结果是没有影响的。所以这道题只需要对所有的可操作区间(即长度为K的区间)考虑是否需要反转。

考虑最左边的牛,当它面朝前时无需反转,当它面朝后时,就反转[1, K]区间一次。然后继续考虑第二头牛即可。

反转的时候不必每头牛都操作一次,只需用一个turns来记录当前区间的反转次数,考虑的下一头牛的状态就由它本身状态+turns的值来决定。随着区间往右移动,我们用区间左右更改的地方来更新turns即可。复杂度为O(n ^ 2)

source 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

#include <cstring>
const int maxn = 5500;
const int INF = 100243535;
int a[maxn], f[maxn], cnt[maxn];
int () {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
char s[10];
scanf("%s", s);
a[i] = (s[0] == 'F' ? 0 : 1);
}
for (int k = 1; k <= n; k++) {
memset(f, 0, sizeof(f));
int turns = 0;
for (int i = 0; i < n; i++) {

if ((a[i] + turns) % 2 == 1) {
if (i + k > n) {
cnt[k] = INF;
break;
}
f[i] = 1;
cnt[k]++;
turns++;
}
if (i - k + 1 >= 0) turns -= f[i - k + 1];

}
}
int ansK = 1;

for (int k = 2; k <= n; k++) if (cnt[k] < cnt[ansK]) ansK = k;

printf("%d %dn", ansK, cnt[ansK]);

}

原文:大专栏  POJ 3276 [Face The Right Way] 题解


上一篇:【全程NOIP计划】数学推导选讲


下一篇:牛客挑战赛 53 B