翻盖有奖:将一列碗翻成口朝上,一把下去可能同时反转3个或2个(首尾),求最小翻转次数。
3.2常用技巧精选(一)
反转
似乎穷举也能过,不过太蠢了。反转法只需枚举2次,分别是从第一个开始翻和从第二个开始翻。反转法跟尺取法其实有点像,都是限定一个区间,往前挪动,尾部挪动之后,需要减掉尾部的影响。
#include <iostream> #include <algorithm> using namespace std; #define MAX_BOW 20 + 1 // 逻辑上多1个,多的这个讨论 int dir[MAX_BOW]; // 方向:1下0上 int f[MAX_BOW]; // 区间[i, i + K -1]是否进行翻转 // 固定K=3,求最少翻转次数,first表示第0个的方向 // INT_MAX表示不可能 int calc(const int& first) { const int N = MAX_BOW; memset(f, 0, sizeof(f)); dir[0] = first; int res = 0; int sum = 0; // f的和 for (int i = 0; i < N - 1; ++i) { // 计算区间[i, i + K -1] if ((dir[i] + sum) & 1) { // 翻转 ++res; f[i] = 1; } sum += f[i]; if (i - 2 >= 0) { sum -= f[i - 2]; } } // 检查剩下的 if ((dir[N - 1] + sum) & 1) { return INT_MAX; } return res; } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif for (int i = 1; i < MAX_BOW; ++i) { cin >> dir[i]; } cout << min(calc(0), calc(1)) << endl; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
12883342 | hankcs | 3185 | Accepted | 244K | 32MS | C++ | 1126B | 2014-05-16 14:17:47 |
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 3185 The Water Bowls 题解 《挑战程序设计竞赛》