草庐IT

Acwing 327. 玉米田

呆唯可可爱爱 2023-03-28 原文

算法分析

棋盘型状态压缩dp

这类dp有一个通用的状态表示法：f[i][j][k],表示前i行（放了j个棋子后）的状态表示为k。

由于本题无棋子要求，因此可以省去中间一维，
即:
  用f[i][j]表示前i行土地的状态为j。


首先由于玉米地有不肥沃的地方不能种植，因此需要通过二进制表示出来可以种植和不可以种植的地方，
我们是将整行用一个二进制数表示的，可种为0，不可种为1，在输入的时候即可判断：
  g[i] += (!x<<(j-1)) //g[i]为每一行土地的二进制表示
由于是棋盘型，因此根据我们的经验显而易见可以知道需要分别分析棋盘的列和行：

根据题意相邻的两格内不能同时种玉米可知：
  （以x为当前格）则  (x&x>>1)=0;
   这很容易理解，比如x的二进制表示为1101，则x>>1 = 0110,可以得出x&x>>1的结果和题目要求相同；

再分析每一列，由于上下列不能同时种玉米：
  (y为相同列不同行的玉米地）因此(y&y-1)=0;



T.T好累
先看代码吧：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=13,mod = 1e8;
int f[N][1<<N];
int g[N];
vector<int> state;
vector<int> le_state[1<<N];
bool check(int x)
{
    return !(x&x>>1);
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            int x;
            scanf("%d",&x);
            g[i]+=(!x<<(j-1));   
            cout<<g[i]<<endl;
        }
    }
    
    for(int i=0;i<(1<<m);i++) {
        if(check(i)) {
            state.push_back(i);
        }
    }
    
    for(int i=0;i<state.size();i++) {
        for(int j=0;j<state.size();j++) {
            if(!(state[i]&state[j])) {
                le_state[i].push_back(j);
            }
        }
    }
    
    f[0][0]=1;
    for(int i=1;i<=n+1;i++) {
        for(int j=0;j<state.size();j++) {
            if(state[j]&g[i]) continue;
            for(int b=0;b<le_state[j].size();b++) {
                f[i][j] = (f[i][j] + f[i-1][le_state[j][b]])%mod;
            }
        }
    }
    
    cout<<f[n+1][0];
    return 0;
}
Acwing327ltstateintC++

有关Acwing 327. 玉米田的更多相关文章

  1. 《蓝桥杯每日一题》背包dp·AcWing3382. 整数拆分 - 2

    1.题目一个整数总可以拆分为2的幂的和。例如：7可以拆分成7=1+2+4,7=1+2+2+2,7=1+1+1+4,7=1+1+1+2+2,7=1+1+1+1+1+2,7=1+1+1+1+1+1+1共计6种不同拆分方式。再比如：4可以拆分成：4=4,4=1+1+1+1,4=2+2,4=1+1+2。用f(n)表示nn的不同拆分的种数，例如f(7)=6。要求编写程序，读入n，输出f(n)mod10的9次。输入格式一个整数n。输出格式一个整数，表示f(n)mod10的9次。数据范围1≤N≤106输入样例：9输出样例：6AcWing3382.整数拆分2.思路这个题目也可以用背包dp求，2的n次幂就是每一

  2. 【蓝桥杯集训·每日一题】 AcWing 3996. 涂色 - 2

    文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴区间DPUnique函数一、题目1、原题链接3996.涂色2、题目描述有n个砖块排成一排，从左到右编号为1∼n。其中，第i个砖块的初始颜色为ci。我们规定，如果编号范围[i,j]内的所有砖块的颜色都相同，且当第i−1和第j+1个砖块存在时，这两个砖块的颜色和区间[i,j]的颜色均不同,则砖块i和j属于同一个连通块。例如，[3,3,3]有1个连通块，[5,2,4,4]有3个连通块。现在，要对砖块进行涂色操作。开始所有操作之前，你需要任选一个砖块作为起始砖块。每次操作：任选一种颜色。将最开始选定的

  3. Acwing 第 91 场周赛 - 2

    Poweredby:NEFUAB-INB站直播录像！Link文章目录Acwing第91场周赛AAcWing4861.构造数列题意思路代码BAcWing4862.浇花题意思路代码CAcWing4863.构造新矩阵题意思路代码Acwing第91场周赛AAcWing4861.构造数列题意略思路将每个数的每一位全部拆出来即可代码/**@Author:NEFUAB-IN*@Date:2023-02-1818:59:30*@FilePath:\Acwing\91cp\a\a.cpp*@LastEditTime:2023-02-1819:03:25*/#includeusingnamespacestd;#d

  4. acwing蓝桥杯 - 数学知识【下】 - 2

     目录欧拉函数快速幂求组合数I博弈论        Nim游戏欧拉函数 在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目，记作φ(n). φ(1)=11、分解质因子，求出质因子p2、将p带入，套公式为了代码方便，套第三个公式#includeusingnamespacestd;intphi(intx){intres=x;for(inti=2;i1)res=res/x*(x-1);returnres;}intmain(){intn;cin>>n;while(n--){intx;cin>>x;cout 补充：若a与m互质 ，则有快速幂 大佬算法讲解： 举个栗子： 如上例所示：利用a取

  5. android - 如何与 OBD II ELM327 适配器​​进行连续通信？ - 2

    目前我正在开发一个应用程序，我已经与OBDIIELM327适配器​​建立了连接，并且可以从OBDII读取数据。例如我使用OBD命令“010C”来获取车辆的转速。我想检索实时数据，例如车辆的速度或转速。这就是我卡住的地方。我没有得到-“如何从车辆中持续获取此类实时数据？我知道，OBDII正在响应我的每一个AT或OBD命令。我的想法是，如果我重复向OBDII适配器发送任何命令，它每次都会发回数据。谁能告诉我，我如何发送单个命令，例如连续“010C”？我应该使用哪种方法从车辆中获取真实数据？拜托，有人指导我解决这个问题。任何指导都会有很大帮助。谢谢。 最佳答案

  6. android - 在 android 中与 ELM327 建立连接后无法向 ELM327 发送 AT 命令 - 2

    我已经编写了一段代码，它能够成功找到配对的OBD并与ELM327建立连接，但是当我尝试发送ATZ命令时，应用程序崩溃了。这是代码fragment，我可能做错了publicHashMapstartOBDCommunicator(BluetoothSocketbtSocketConnected,StringparamClassName,StringmethodName){HashMapdataRetriever=newHashMap();sendDataToOBD(btSocketConnected,"ATZ\r");dataRetriever.put("Reset",readDataFr

  7. android - 从 ELM327 中提取数据 - 2

    正在开发一个应用程序，我可以从ELM327获取数据并将其显示在android设备上。但我有疑问，ELM327是不可控的，我的意思是它不能自动向android设备发送数据，所以怎么会我能够从ELM327中提取数据。我真的被困在这里。所以帮助将不胜感激。谢谢!任何人都可以帮助我了解我必须在android中使用的命令类型以从ELM327获得响应吗？我如何只接收速度和rpm？我如何读取该数据并将其显示在android设备上？ 最佳答案 ELM设备是一种命令/响应设备，它需要您发送命令以便ELM处理它，与ECU系统通信，然后格式化并将响应返回

  8. android - 如何使用 OBD2 (ELM327) 实现应用程序，如 Android 中的 Torque？ - 2

    我对obd2和elm327很陌生。我需要开发一个应用程序来使用obd2(蓝牙)和elm327获取汽车信息。请任何人帮忙。提前致谢。 最佳答案 欢迎使用Stackoverflow!你的问题有点宽泛。在我维护蓝牙OBDAndroid应用程序时，我会给你一些指导。从BluetoothChat开始示例应用程序以了解与蓝牙串行设备通信的基础知识。然后研究ELM327ProgrammersGuide了解协议(protocol)的细节。结帐existingprojects的想法。 关于android-

  9. android - 使用 BluetoothChat 与 ELM327 通信 - 2

    我目前正在尝试通过BluetoothChat示例应用程序与ELM327OBDII蓝牙加密狗进行通信。我可以连接，因为我已经更改了UUID，但是我只能收到启动命令和提示“>”来发送命令，每当我尝试发送命令时，我都会收到以下信息CANOBDII:ELM327v1.2a>我:ATRVCANOBDII:ATRVCANOBDII:>CANOBDII:?现在我在此处阅读以将“\r”附加到命令，但是当我这样做时，我得到了完全相同的响应。我正在使用示例应用程序“BluetoothChat”主类...publicclassBluetoothChatextendsActivity{//Debuggingp

  10. AcWing第98和99周赛 - 2

    第98场周赛竞赛-AcWing 1、大整数4947.大整数-AcWing题库 题目给定两个整数 n,k。请你输出一个 n 位数，要求其各位数字均为 k。输入格式共一行，包含两个整数 n,k。输出格式一个整数，表示满足要求的 n位数。数据范围前三个测试点满足 1≤n≤3。所有测试点满足 1≤n≤100，1≤k≤9。输入样例：32输出样例：222 简单题直接看代码吧！ 代码importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc

随机推荐