poj 3276 Face The Right Way 挑战150 反转-白红宇

poj 3276 Face The Right Way 挑战150 反转

阅读量：4113 次

发布时间：2019-05-25

本文共 2365 字，大约阅读时间需要 7 分钟。

题意：给你n头牛，牛有B,F两种状态，每次能使连续的k头牛状态变反，，求最小的操作次数m及其对应的最小k；

分析：反转问题，建模很关键，

记得f[i]表示第i 头牛是否需要反转，sum表示i之前的牛反转的次数对其的影响；一个sum可以降低复杂度，由0(n^3)降为o(n^2)

；

#include #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                
                  #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const int inf = 0x3f3f3f3f; using namespace std; int dir[5005],f[5005]; int n; char s[3]; int solve(int k) { memset(f, 0, sizeof(f)); int sum = 0, m = 0; for (int i = 1; i <= n - (k - 1); i++) { if ((sum + dir[i]) % 2 == 1) { m++; f[i] = 1; } sum += f[i]; if (i - k + 1 >= 1) sum -= f[i - (k - 1)]; } for (int i = n - (k-2) ; i <= n; i++) { if ((sum + dir[i]) % 2 == 1) return -1; if (i - k + 1 >= 1) sum -= f[i - (k - 1)]; } return m; } int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) { scanf("%s", s); if (s[0] == 'B') dir[i] = 1; else dir[i] = 0; } int k,temp, m = inf; for (int i = 1; i <= n; i++) { temp = solve(i); if (temp < m&&temp >= 0) { m = temp; k = i; } } if (m == inf) printf("-1\n"); else printf("%d %d\n",k,m); } return 0; }

wa:

#include 
     
       #include 
      
        #include
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  #include 
                 
                   #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const int inf = 0x3f3f3f3f; using namespace std; int dir[5005],f[5005],sum[5005]; int n; char s[3]; int solve(int k) { memset(sum, 0, sizeof(sum)); for (int i = 1; i <= n; i++) { if (dir[i] == 1) f[i] = 1; else f[i] = 0; } int m = 0; f[0] = 0; for(int i = 1; i <= n-(k-1); i++) { if ((sum[i] + f[i]) % 2 == 1) { m++; sum[i+1]++; } sum[i] -= sum[i-(k-1)]; sum[i + 1] += sum[i - 1]; } for (int i = n - (k - 2); i <= n; i++) if ((sum[i] + f[i]) % 2 == 1) return -1; return m; } int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) { scanf("%s", s[i]); if (s[0] == 'B') dir[i] = 1; else dir[i] = 0; } int k,temp, m = inf; for (int i = 1; i <= n; i++) { temp = solve(i); if (temp < m&&temp >= 0) { m = temp; k = i; } } if (m == inf) printf("-1\n"); else printf("%d %d",k,m); } return 0; }