POJ 3185 (The Water Bowls)

点击打开链接

题目意思：

翻碗（其实就是开关问题），题目说了定能找到一种方法使得碗全部被翻过来，所以不用考虑无解的情况。

因此我们可以找到一个规律，如果当前该点为1，则翻下面一个点，那么我们可以知道这个方法得到的肯定是最优解（这里不证明），但是要注意一下数据

例如  1 1 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 如果我们还这么翻则要多做很多次，其实上只要一次即翻第一个即可，那么我们要算出 从左到右 和 从右到左 （其实就是枚举第一个位置按与不按）的次数找到最小值

就是我们所要的最小值

代码1（直接贪心枚举两种情况）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int num[25] , tem[25];

int min(int a , int b){
    return a < b ? a : b;
}
void Min(){
    int i , j;
    int min1 = 0, min2 = 0;//min1和min2分别存储两种操作次数

    //从左到右

    for(i = 1 ;i <= 20 ; i++){
        if(num[i-1]){
            num[i] = !num[i];
            num[i-1] = !num[i-1];
            num[i+1] = !num[i+1];
            min1++;
        }

    }

    //从右到左
    for(i = 19 ; i >= 0 ; i--){
        if(tem[i+1]){
            tem[i] = !tem[i];
            tem[i-1] = !tem[i-1];
            tem[i+1] = !tem[i+1];
            min2++;
        }
    }
    cout<<min(min1 , min2)<<endl;
}
int main(){
    int i , j;
    while(scanf("%d" , &num[0]) != EOF){
        tem[0] = num[0];
        for(i = 1 ; i < 20 ; i++){
            scanf("%d" , &num[i]);
            tem[i] = num[i];
        }
        Min();
    }
    return 0;
}