poj 3276 反转开关问题(一) DP+模拟

题意：n头牛，F表示朝前，B表示朝后，每次可以让连续的k头牛变换方向，要使所有的牛都朝前，求最小的转向次数及此时的k

Sample Input

7
B
B
F
B
F
B
B

Sample Output

3 3

穷举肯定是要超时的 2^n个状态...但是先思考一些规律吧：
1、转动奇数次，必然与初始方向相反；

2、转动偶数次，必然与初始方向相同；

枚举k:1-n,得到O(n^3)的代码：（这个代码会超时，只是模拟而已）

//TLE  O(n^3)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; #define MAXN 5005 int s[MAXN]; int n; int test(int k) { int i,j,ans=0; for(i=0;i=0&&m
      
       
 
       
 
 再做处理是可以降低时间复杂度的
       
f[i] 表示从i-k+1到i头牛的反转情况，值为1表示反转，值为0表示没有反转
       
那么sum=f[i-k+1]+f[i-k+2]+...+f[i-1]，如果sum为基数，那么转动奇数次，必然与初始方向相反，如果sum为偶数，必然与初始方向相同。
       
于是省去一重循环，得到O(n^2)的代码 AC
       
 
       
#include 
        
         
#include 
         
           #include 
          
            #include 
           
             using namespace std; #define MAXN 5005 int s[MAXN]; int f[MAXN]; int n; int test(int k) { int i,j,ans=0,sum=0; memset(f,0,sizeof(f)); for(i=0;i
            
             =0) sum-=f[i-k+1]; } for(i=n-k+1;i
             
              =0) sum-=f[i-k+1]; } //if(!s[i]) // return -1; return ans; } int main() { int i,len,kmin,m,mmin,k; char cow[MAXN]; while(scanf(%d,&n)!=EOF) { memset(s,0,sizeof(s)); mmin = MAXN; m=-1; for(i=0;i=0&&m