AcWing 95 费解的开关

2021-02-05 11:16

阅读：655

标签：压缩 com i+1 状态压缩思路 ++ bool while cpp

前言
题目链接
思路
代码

前言

博客咕咕咕了好久了，是时候写一下了

题目链接

AcWing 95 费解的开关

思路

首先可以看出

1.每一个位置顶多只会操作一次。因为如果操作两次的话，相当于不操作，必然是不满足最优解
2.在一套方案中，操作的顺序无关紧要。
3.如果我们确定了第I行的操作方案的话，那么后面的行数都可以依此递推，下面给出一个详细的解答。

11011
10110
01111
11111
比如说这个例子，如果我们确定了第1行，那么第二行所有的0(坐标：a[i][j])
都只能是第三行a[i+1][j]来修改了，因为如果你第二行修改的话，那么第一行将会打乱，下面每一行依此类推。

然后再利用状态压缩，就可以了

代码

#include 
using namespace std;
int n,m,i,j,k,a[7][7],ans1=1e6,b[7][7];
void read() {
    getchar();
    for (i=1; i>n;
    while(n--) {
        read();
        for (i=0; i>(j-1) & 1) {
                    ans++;
                    a[1][j-1]^=1,a[1][j+1]^=1,a[1][j]^=1,a[2][j]^=1;
                }
            for (j=1; j=1; k--)
                    if (!a[j][k]) {
                        ans++;
                        a[j][k]^=1,a[j+2][k]^=1,a[j+1][k]^=1,a[j+1][k+1]^=1,a[j+1][k-1]^=1;
                    }
            bool ok=true;
            for (j=1; j6)
            cout

AcWing 95 费解的开关

标签：压缩 com i+1 状态压缩思路 ++ bool while cpp

原文地址：https://www.cnblogs.com/pyyyyyy/p/11444585.html

上一篇：csv解析框架Windmill的一个demo

下一篇：webapi测试

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 95 费解的开关
文章链接：http://soscw.com/index.php/essay/51307.html

亲，登录后才可以留言！

AcWing 95 费解的开关

前言

题目链接

思路

代码

评论

热门文章

推荐文章

最新文章

置顶文章