poj 3185 The Water Bowls 反转（开关）-白红宇

poj 3185 The Water Bowls 反转（开关）

阅读量：4114 次

发布时间：2019-05-25

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

有20个碗排成一排，有些碗口朝上，有些碗口朝下。每次可以反转其中的一个碗，但是在反转该碗时，该碗左右两边的碗也跟着被反转（如果该碗为边界上的碗，则只有一侧的碗被反转）。求最少需要反转几次，可以使得所有碗口均朝上。

#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 a1[25], a2[25]; int solve() { int ans1= 0,ans2=0; memcpy(a2, a1, sizeof(a1)); for (int i = 2; i <= 20;i++) if (a1[i - 1] % 2 == 1) { a1[i]++; a1[i + 1]++; ans1++; } if (a1[20] % 2 == 1) ans1 = inf; ans2++; a2[1] = 1 - a2[1]; a2[2] = 1 - a2[2]; for (int i = 2; i <= 20;i++) if (a2[i-1]%2==1) { a2[i]++; a2[i + 1]++; ans2++; } if (a2[20] % 2 == 1) ans2 = inf; return ans1 < ans2 ? ans1: ans2; } int main() { memset(a1, 0, sizeof(a1)); memset(a2, 0, sizeof(a2)); while (~scanf("%d",&a1[1])) { for (int i = 2; i <= 20; i++) scanf("%d", &a1[i]); printf("%d\n", solve()); } return 0; }

分析：反转问题最关键的是枚举最初状态，因为后面的状态都可以由前一状态推出，而最初状态

是需要枚举的，，因为题意中后面的状态可以影响到前面的状态的，故最初状态只能枚举确定；

wa代码：

#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 a[25],f[25]; int solve() { int ans = 0; memset(f, 0, sizeof(f)); for (int i = 1; i <= 18;i++) if ((a[i] + f[i]) % 2 == 1) { f[i + 1]++; f[i + 2]++; ans++; } if ((a[19] + f[19]) % 2 == 1) ans++; return ans; } int main() { for (int i = 1; i <= 20; i++) scanf("%d", &a[i]); printf("%d\n", solve()); return 0; }

转载地址：http://vvgsi.baihongyu.com/

你可能感兴趣的文章