POJ3276 Face The Right Way 开关问题

①每个K从最左边进行考虑

②f[i]=[i,i+k-1]是否进行反转:1代表是,0代表否

∑ (i)(i=i+1-K+1) f[j]=∑ (i-1)(i=i-K+1) f[j]+f[i]-f[i-K+1]

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<queue>
 5 #include<map>
 6 #include<vector>
 7 #include<set>
 8 #include<string>
 9 #include<cmath>
10 #include<cstring>
11 using namespace std;
12 int n;
13 int dir[5005],f[5005];//dir牛的方向0F1B,f是[i,i-k+1]是否反转
14 int cal(int k)//k求最小操作数
15 {
16     memset(f,0,sizeof(f));
17     int res=0;
18     int sum=0;//f的和
19     for(int i=0;i+k<=n;i++)
20     {
21         if((dir[i]+sum)%2!=0)
22         {
23             res++;
24             f[i]=1;
25         }
26         sum+=f[i];
27         if(i-k+1>=0)
28         {
29             sum-=f[i-k+1];
30         }
31     }
32     //检查后面的牛有没有朝后
33     for(int i=n-k+1;i<n;i++)
34     {
35         if((dir[i]+sum)%2!=0)
36         {
37             return -1;//无解
38         }
39         if(i-k+1>=0)
40         {
41             sum-=f[i-k+1];
42         }
43     }
44     return res;
45 }
46 void solve()
47 {
48     int resK=1,resM=n;
49     for(int k=1;k<=n;k++)
50     {
51         int m=cal(k);
52         if(m>=0&&resM>m)
53         {
54             resM=m;
55             resK=k;
56         }
57     }
58     printf("%d %d\n",resK,resM);
59 }
60 int main()
61 {
62     scanf("%d",&n);
63     for(int i=0;i<n;i++)
64     {
65         getchar();
66         char c=getchar();
67         if(c==‘B‘)
68             dir[i]=1;
69         else
70             dir[i]=0;
71     }
72     solve();
73     return 0;
74 }

原文地址:https://www.cnblogs.com/fudanxi/p/12231006.html

时间: 01-23

POJ3276 Face The Right Way 开关问题的相关文章

挑战程序竞赛 反转开关 poj3276

这个我其实也没有看太懂它的证明过程. 1.若某一个位置被翻转了n次,则其实际上被翻转了n%2次. 2.分析易知翻转的顺序并不影响最终结果. 3.现在我们着眼于第1个位置,可知若要将第1个位置进行翻转只有翻转它自己,因为没有其他位置的翻转会引起它的翻转. 由①可知若第1个位置为1则必须且进行翻转(并将其后2个进行连带翻转)且以后不再进行翻转,因为再进行翻转就一共翻转了2次相当于没翻转. 然后着眼于第2个位置,由于第1个位置不再进行翻转,所以要想翻转第2个位置只有翻转它自己,因为没有其他位置的翻转会

翻转问题(开关,开灯问题)求解技巧

转载自:http://blog.csdn.net/ac_hell/article/details/51077320 翻转问题技巧详解 例.给定一个01串,现有翻转规则:翻转某一个位置时其后面2个位置也会跟着翻转,也就是每次翻转都会翻转3个连续的位置.要将01串全部翻转为0,求最小的翻转次数 形似这类题的问题叫做翻转问题,也可以叫开关问题,对于这类题通常都会用到下面我要说的方法来解 ①.若某一个位置被翻转了n次,则其实际上被翻转了n%2次,因为翻转2k次相当与没翻转,翻转2k+1次相当于翻转了1次

【反转】POJ3276

Face The Right Way 题意:N个牛 每个都有一定的方向 B背对 F表示头对着你 给你一个装置 每次可以选择连续的K个牛反转方向 问你如何选择K 使得操作数最少 k也应尽量小. 例子:   N=7   BBFBFBB   (F:前面   B:后面)    (红色的为要反转的)   此出K=3  M=3 B B F B F B B F F B B F B B F F F F B B B F F F F F F F   成功了 如果用暴力的方法的话:   考虑N头牛的话最坏情况下要进行

The Water Bowls [POJ3185] [开关问题]

题意 一串长度为20的0,1数列,每次翻转i,会影响i-1,i+1,也被翻转,最少翻转成0的步骤数是多少? Sample Input 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 Sample Output 3 分析 这一道开关问题和POJ3276很类似,但是那个是有固定长度的,我们可以看做是一个点向后的一个区间进行翻转,就不会对前面产生影响. 这道题就不一样,会影响前面的,那我们就看做是i为作用点,i+1,i+2为附带效应点,就可以转换成上面那种类型了.只是要

基于Redis bitmap实现开关配置功能

作者:zhanhailiang 日期:2014-12-21 bitmap api SETBIT key offset value 对key所储存的字符串值,设置或清除指定偏移量上的位(bit). 位的设置或清除取决于value参数,可以是0也可以是1. 当key不存在时,自动生成一个新的字符串值. 字符串会进行伸展(grown)以确保它可以将value保存在指定的偏移量上. 当字符串值进行伸展时,空白位置以0填充. offset参数必须大于或等于0,小于2^32(bit映射被限制在512MB之内

开关中断与cpsid/cpsie指令

在汇编代码中,CPSID   CPSIE  用于快速的开关中断. CPSID I ;PRIMASK=1, ;关中断 CPSIE I ;PRIMASK=0, ;开中断 CPSID CPSIE F F ;FAULTMASK=1, ;FAULTMASK=0 ;关异常 ;开异常 I:IRQ中断;    F:FIQ中断 最常见的这两个命令的使用处是在关中断.开中断的实现中,我们经常用的local_irq_save和local_irq_restore最终都是调用了以下两个实现,即关/开中断只是操作了CP

Android5.0以上系统的移动网络开关

笔者近期遇到一个非常有意思的bug,贴出来和大家分享下. 那是一个温暖的早晨,阳光晒得人非常舒服.一封bug邮件像一片叶子飘到我的邮箱. 一番交流.笔者确认负责的Widget开关在Android5.0以上系统没有作用.相信非常多做过移动网络开关的朋友都知道.传统的方法是在ConnectivityManager中通过反射两个方法setMobileDataEnabled和getMobileDataEnabled来控制移动网络开和关的. /** * Gets the value of the sett

Gym 100712I Bahosain and Digits(开关翻转问题)

http://codeforces.com/gym/100712/attachments 题意: 给出一串数字,每次选择连续的k个数字加上任意数(超过10就取余),最后要使得所有数字都相等,求最大的k. 思路: 开关翻转问题. 算法具体可以参考<挑战程序竞赛>常用技巧篇. 这道题目就是在枚举k的同时再枚举一下最后要转换成的数字即可. 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring>

微信小程序组件解读和分析:十五、switch 开关选择器

switch 开关选择器组件说明: switch,开关选择器.只能选择或者不选.这种属于表单控件或者查询条件控件. switch 开关选择器示例代码运行效果如下: 下面是WXML代码: [XML] 纯文本查看 复制代码 ? 01 02 03 04 05 06 07 08 09 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 <view class="secti