一维的开关问题

题目1:http://poj.org/problem?id=3276

这题需要求对于特定的k,让所有牛都面朝前方所需的最小操作次数。要明确的是:对于同一个区间,进行两次以上的翻转,没有意义,因此我们确定一头牛是正向还是反向,可以看他的翻转次数。并且,交换区间的翻转顺序对结果没有影响。

先考虑最左端的牛,如果他面朝前方,那就不需要翻转,问题规模-1。如果它面朝后方,则翻转,然后向右找到下一个面朝后方的牛,继续执行上面的操作。

但是,这样子的时间复杂度是O(N3),因此我们需要优化。我们可以用一个数组f[i]来表示[i, i+K-1]这个区间上的牛是否进行了翻转(他们在这次翻转中,是一个整体),然后维护一个sum,记录当前牛经过了几次翻转,那么时间复杂度可以优化到O(N2).

AC代码

#include <string.h>
#include <iostream>
using namespace std;
#define MAXN 5005

int a[MAXN];
int n;
int f[MAXN]; //代表[i, i+k-1]被翻转的次数
int main()
{
    scanf("%d", &n);
    char tmpc;
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", &tmpc);
        if (tmpc == 'B')
            a[i] = 1;
        else
            a[i] = 0;
    }

    int ansk = MAXN, minm = 100 * MAXN;
    for (int k = 1; k <= n; ++k)
    {
        int sum = 0;
        int m = 0;
        memset(f, 0, sizeof(f));
        for (int i = 0; i + k <= n; ++i)
        {
            if ((a[i] + sum) % 2 != 0)
            {
                //当前的牛面朝后方,将其反转
                ++m;
                f[i] = 1;
            }
            sum += f[i];
            if (i - k + 1 >= 0)
                sum -= f[i - k + 1];
        }

        for (int i = n - k + 1; i < n; ++i)
        {
            //检查剩下的牛是否满足情况
            if ((sum + a[i]) % 2 != 0)
            {
                //无解
                m = -1;
            }
            else
            {
                sum -= f[i - k + 1];
            }
        }
        if (minm > m && m >= 0)
        {
            minm = m;
            ansk = k;
        }
    }
    printf("%d %d\n", ansk, minm);
}

二维的开关问题

题目:http://poj.org/problem?id=3279

还是和上面的类似,同一个格子翻转两次以上是没有意义的。然后,和上面那题类似的思路。在上面那题中,让最左端的牛翻转的方法只有1种,但是,在这个问题里,最左上角的格子有两种翻转方式。那怎么办?我们可以先确定好第一行的翻转方式,然后从第二行开始翻转,只要当前格子的上方的格子是黑色的,那就翻转当前格子。然后,最后就检查一下最后一行,是否全为白色,如果全为白色则不行。

这里涉及到一个生成集合的方法,待会专门写一篇博文来记录一下。

AC代码

#include <iostream>
#include <string.h>
using namespace std;

typedef long long ll;
#define MAXN 17
int mp[MAXN][MAXN];
int op[MAXN][MAXN];
int opt[MAXN][MAXN];
const int dx[5] = {0, 0, 0, 1, -1};
const int dy[5] = {0, 1, -1, 0, 0};

int n, m;

bool get(int x, int y)
{
    //判断(x,y)的颜色
    int cnt = int(mp[x][y]);
    for (int i = 0; i < 5; ++i)
    {
        int x2 = x + dx[i], y2 = y + dy[i];
        if (0 <= x2 && x2 < m && 0 <= y2 && y2 < n)
            cnt += op[x2][y2];
    }
    return cnt % 2;
}
int calc()
{
    for (int a = 1; a < m; ++a)
    {
        for (int b = 0; b < n; ++b)
        {
            if (get(a - 1, b) != 0)
            {
                //当前格子上一行的格子是黑色的,需要翻转当前格子
                op[a][b] = 1;
            }
        }
    }
    for (int j = 0; j < n; ++j)
    {
        if (get(m - 1, j))
        {
            //最后一行还有黑色格子,无解
            return -1;
        }
    }

    int ans = 0;
    for (int a = 0; a < m; ++a)
    {
        for (int b = 0; b < n; ++b)
        {
            if (op[a][b])
                ++ans;
        }
    }

    return ans;
}
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &mp[i][j]);
    int res = -1;
    for (int i = 0; i < (1 << n); ++i)
    {
        memset(op, 0, sizeof(op));
        //生成第一行的各种翻转方式
        for (int j = 0; j < n; ++j)
        {
            op[0][n - j - 1] = (i >> j) & 1;
        }

        int num = calc();

        if (num >= 0 && (res < 0 || res > num))
        {
            res = num;
            memcpy(opt, op, sizeof(op));
        }
    }
    if (res < 0)
    {
        printf("IMPOSSIBLE\n");
    }
    else
    {
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                printf("%d ", opt[i][j]);
            }
            printf("\n");
        }
    }
}

转载请注明来源:https://www.longjin666.top/?p=1192

你也可能喜欢

发表评论