POJ 3276 (开关问题)

发表于 | 分类于 | 阅读次数:
字数统计: 790 字

这道题本来是挑战上面一道经典的例题，这次在Google 的code jam的资格赛里面也出现了。可气的是我忘记怎么做了，只好重新看一遍挑战的书，下面讲一讲我对这道题的理解吧。

题意

给出了N头牛的朝向（朝前或者朝后），现有一台机器，可以一次性反转连续的k头牛的朝向，最终要使得所有的牛的朝向都是朝前的，现在问使得反转次数最少的k的取值和最小的反转次数。

题解

一个区间的反转会导致区间内的所有牛的朝向都改变，反转区间的顺序对最后的结果是没有影响的。同时对于一个区间要么就不反转，要么就只反转一次,不可能有两次或者以上的反转。一头牛是否需要反转是由这头牛一开始的状态以及其他区间的反转对这头牛的影响决定的。所以我们每次都考虑区间中最左边的牛，根据初始的朝向以及其他区间反转对这头牛的影响决定这头牛是否要反转，后面我们就不需要考虑这头牛，只要区间是否反转给后面的牛考虑带来的影响。这样每次每次问题的规模就减少了1。
我们设f[i]: 区间[i,i+K-1]是否进行反转，是为1，否则为0
这样我们考虑到第i头牛的时候，就是考虑f[i-K+1]-f[i-1]对它的影响，将这些值相加，然后再加上牛本身的状态，为奇数时改变朝向，为偶数时不需要改变，这样我们就可以得到f[i]的值了，f[i]继续影响后面的牛的决策。

代码

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
69
70
71
72
73
74
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

const int maxn=5006;

int dir[maxn],f[maxn];    //存放初始状态和反转情况
int N;

int calc(int k)
{
	memset(f,0,sizeof(f));
	int res=0;        //最后反转的次数
	int sum=0;        //之前区间的反转对当前节点的影响数
	for(int i=0;i+k<=N;i++)
	{
		if((dir[i]+sum)%2)    //需要进行反转
		{
			res++;
			f[i]=1;         //会对后面的产生影响
		}
		sum+=f[i];
		if(i-k+1>=0)
			sum-=f[i-k+1];
	}
	for(int i=N-k+1;i<N;i++)  //无法进行反转的阶段
	{
		if((dir[i]+sum)%2)
			return -1;    //无解
		if(i-k+1>=0)
			sum-=f[i-k+1];
	}
	return res;	
}

void solve()
{
	char ch[2];
	while(scanf("%d",&N)!=EOF)
	{
		for(int i=0;i<N;i++)
		{
			scanf("%s",&ch);
			if(ch[0]=='F')
				dir[i]=0;
			else
				dir[i]=1;
		}
		int minid=1,minva=N;
		for(int k=1;k<=N;k++)
		{
			int tmp=calc(k);
			if(tmp>=0 && tmp<minva)
			{
				minva=tmp;
				minid=k;
			}
		}
		printf("%d %d\n",minid,minva);
	}
}

int main()
{
    freopen("input.txt","r",stdin);
    solve();
    return 0;
}