说是动态规划，实质上应该叫记忆化搜索，本质上还是搜索

一、

种稻子的题目

基本上是01规划问题；

枚举法，2^(n*m)次方

使用动态规划状态转移，将复杂度降为 n * 2^(m)^2

先来看一个简单的例子

如果有面积为1*n的一行格子给你填充，可以填充的方块有1*1的 和 1*2的问有多少种填充方法设DP[j][0]表示第j格没被放的方案数则DP[j][1]表示第j格不能再放了。这里j是阶段0和1是状态我们考虑当前两格的放法那么状态转移就是DP[j+1][1]=2*DP[j][0](这样在j和j+1放1*2的方块或者放两个1*1的方块)+DP[j][1](这样在j+1放1*1的方块);DP[j+1][0]=DP[j][1];当然还可以不放那ans=DP[n][1]+DP[0];

和上面的例子类似，这里我们取一行为一个阶段，每一行的所有列为一个状态，

所以这里的状态是一行的01变量，刚好可以用2进制数来表示以及进行逻辑运算

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define mem(x) memset(x,0,sizeof(x))using namespace std;const int N=12;const int M=12;const int mod = 1e8;int dp[N][1<<(M)];bool maze[N][M];int n,m;//判断这个状态是否合法，即这一行不冲突，并且和输入不冲突//一行不冲突的情况其实有限，可以预处理出来，可以降低复杂度。/*for(int i=0;i<(1<
         
          7; *由题目意思图上为0,状态为1是不允许的，即位运算的时候01不合法，00，10，11都合法 *这样的位运算，可以用(~7)&state==0 来判断，先对7取反再与状态做与运算。 */bool isok(int i,int j){ int bit=m-1; bool fg=true; int tp=1; int prebit = false; while(bit>=0) { int thebit =(tp&j); //cout<<"tp="<
          
           <<"j="<
           
            <
            
             >n>>m) { mem(maze); for(int i=0;i
             
              >tp; if(tp) { maze[i][j]=true; } } } mem(dp);//第一行单独列出来 for(int j=0;j<(1<

二、炮兵布阵

这题又在上题的基础上把状态转移弄复杂了一点，下面一点一点来分析

首先状态还是和上题一样，

先定义数组

const int N=101;const int M=11;char maze[N][M];int ok[N];const int Max=65;int arr[Max];int cnt[Max];int n,m,top;int dp[N][Max][Max];

基于本题炮兵攻击范围比较大，所以还是先预处理出行合法状态
结果是1024个状态中只有60个合法

void init(){    top=0;    for(int i=0;i<(1<
    
     0)        {            if(tp&1)cnt[i]++;            tp >>=1;        }    }    //for(int i=0;i

输入数据转换

void data_input(){    mem(ok);    for(int i=0;i
    
     >=1;//这里上面多移动了一位、、、、debug了半天        ok[i]=~ok[i];        //cout<
     
      <

状态起点

for(int i=0;i

状态转移方程

//这里因为上一阶段状态对这一阶段状态的影响可以直接根据是否在同一列判断//所以就不用记录状态对下一阶段的影响。//否则还要开数组记录影响//dp[i][k][kk]=max(dp[i-1][kk][j])+cnt[i]写法和上面初始化第二行一样就行了for(int i=1;i
    
     now)now = pre;            }            if(now!=-1)            {                now+=cnt[k];            }        }    }}

输出结果

int ans=0;for(int j=0;j

代码有点长，而且当时写的不是很清醒，讲几个当时调试错误的地方

/*第一次写，用dp[N][Max][2]来记录一行的状态，[0]记录个数，[1]记录上上行的状态然后dp[i]由所有符合上述条件的dp[i-1]转移，ppreState 由 [1] 来读取。*/1. 第一遍的代码是这样写的，然后疯狂WAfor(int i=0;i
    
     now)                {                    now = pre;                    preState = arr[j];                }            }        }        if(now!=-1)        {            now+=cnt[k];        }    }}/*这里我拿第三行来举例这种做法是拿上一行的最优状态转移到这一行，虽然也进行了上上行的状态合法判断，但是遗漏了很多情况，即第三行决策的最优情况不单单由第二行的最优决策决定，而是由前两行加上这一行的最优决策决定。2. (st1&st2)==0 要加括号

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        /*#include 
        
         #include 
         
          #include 
          
           */#define mem(x) memset(x,0,sizeof(x))using namespace std;const int N=101;const int M=11;char maze[N][M];int ok[N];const int Max=65;int arr[Max];int cnt[Max];int n,m,top;int dp[N][Max][Max];void decode(int x){ //if(x<0)x=-x; int tp=0; int arr[32]; mem(arr); while(x>0) { arr[tp++]=int(x&1); x>>=1; } for(int i=tp-1;i>=0;i--)printf("%d%s",arr[i],i==0?"\n":"");}void data_input(){ mem(ok); for(int i=0;i
           
            >=1; ok[i]=~ok[i]; //cout<
            
             <
             
              0) { if(tp&1)cnt[i]++; tp >>=1; } } //for(int i=0;i
              
               >n>>m) { init(); data_input(); memset(dp,-1,sizeof(dp));//这里初始化为-1因为dp可能为0 //第一行 for(int i=0;i
               
                now)now = pre; } if(now!=-1) { now+=cnt[k]; } } } } int ans=0; for(int j=0;j

牛客网上一道纯搜索题

题目描述

随着海上运输石油泄漏的问题，一个新的有利可图的行业正在诞生，那就是撇油行业。如今，在墨西哥湾漂浮的大量石油，吸引了许
多商人的目光。这些商人们有一种特殊的飞机，可以一瓢略过整个海面20米乘10米这么大的长方形。（上下相邻或者左右相邻的格子，不能斜着来）当然，这要求一瓢撇过去的全部是油，如果一瓢里面有油有水的话，那就毫无意义了，资源完全无法利用。现在，商人想要知道，在这片区域中，他可以最多得到多少瓢油。

地图是一个N×N的网络，每个格子表示10m×10m的正方形区域，每个区域都被标示上了是油还是水

就是最大50*50的01地图上，铺1*2的格子，问最多铺几个。

这道题就没法状压，因为N太大了。纯搜索，当时比赛没想到好的思路

赛后看别人代码

#include
    
     using namespace std;char s[60][60];int c0,c1,n;void dfs(int x,int y){    if (x>=n||y>=n||x<0||y<0||s[x][y]=='.') return;    (x+y)&1?++c0:++c1;    s[x][y]='.';    dfs(x+1,y);    dfs(x-1,y);    dfs(x,y+1);    dfs(x,y-1);}int main(){    int t;    scanf("%d",&t);    for (int i=1; i<=t; ++i){        scanf("%d",&n);        int ans=0;        for (int i=0; i

解释
其实很简单，对于每一个有油的连通块，单独求这个连通块的最大覆盖即可。但是当时我不知道怎么求比较好久放着了。
大部分答案的思路就像上面的代码，对于每一个连通块搜索的过程中，用(x+y)&1分成两组的点
不难看出这两组点再地图上相邻，所以取其中一组点，就是最大覆盖，当然，只能取小的那组点。
那min(c0,c1)就是这一个连通块1*2格子的最大覆盖…

三、

整数转2进制

void decode(int x){    int top=0;    int arr[32];    mem(arr);    while(x>0)    {        arr[top++]=int(x&1);        x>>=1;    }    for(int i=top-1;i>=0;i--)printf("%d%s",arr[i],i==0?"\n":"");}