Logo wlc的博客

博客

pyyz头像

2024-05-17 19:56:07 By Cinque Terre wlc

PYYZOJ新增用户头像显示功能，请在个人信息中填写自己的qq号，您的头像PYYZOJ会自动获取！

比赛367

2024-03-30 11:36:39 By Cinque Terre wlc

mod加减乘除

(a+b) mod n = ((a mod n) + (b mod n)) mod n

(ab) mod n = ((a mod n) (b mod n)) mod n

362作业

2024-03-23 10:15:17 By Cinque Terre wlc
mod加减乘除

(a+b) mod n = ((a mod n) + (b mod n)) mod n

(a*b) mod n = ((a mod n) * (b mod n)) mod n

原文链接：https://blog.csdn.net/Encore47/article/details/113776696
//跳房子  2914 2971 98 3031
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
ll s[10][10],a[10],sb[10][10][10][10][10][10];
ll ans;
void solve()
{
    if(!sb[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]])
        sb[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]]++,ans++;
}
void dfs(ll x,ll y,ll t)
{
    a[t]=s[x][y];
    if(t==6) solve();
    else
    {
        if(x<5) dfs(x+1,y,t+1);
        if(x>1) dfs(x-1,y,t+1);
        if(y<5) dfs(x,y+1,t+1);
        if(y>1) dfs(x,y-1,t+1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i=1; i<=5; i++)
        for(int j=1; j<=5; j++)
            cin>>s[i][j];
    for(int i=1; i<=5; i++)
        for(int j=1; j<=5; j++)
        {
            dfs(i,j,0);
        }
    cout<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int s[6][6],ans;;
bool tot[100000];
int fx[5]={0,0,0,-1,1},fy[5]={0,1,-1,0,0};
void dfs(int x,int y,int vis,int cnt)
{
    if(cnt==5)
    {
        if(!tot[vis]) ans++;
        tot[vis]=true;
        return;
    }
    for(int i=1;i<=4;i++)
    {
        int nx=x+fx[i],ny=y+fy[i];
        if(nx<1||nx>5||ny<1||ny>5) continue;
        dfs(nx,ny,vis*10+s[nx][ny],cnt+1);
    }
}
int main()
{
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++) 
            cin>>s[i][j];
    for(int i=1;i<=5;i++) 
        for(int j=1;j<=5;j++) 
            dfs(i,j,s[i][j],0);
    cout<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
ll s[10][10],a[10],sb[10][10][10][10][10][10];
ll ans;
void solve()
{
    if(!sb[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]])
        sb[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]]++,ans++;
}
void dfs(ll x,ll y,ll t)
{
    a[t]=s[x][y];
    if(t==6) solve();
    else
    {
        if(x<5) dfs(x+1,y,t+1);
        if(x>1) dfs(x-1,y,t+1);
        if(y<5) dfs(x,y+1,t+1);
        if(y>1) dfs(x,y-1,t+1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i=1; i<=5; i++)
        for(int j=1; j<=5; j++)
            cin>>s[i][j];
    for(int i=1; i<=5; i++)
        for(int j=1; j<=5; j++)
        {
            dfs(i,j,0);
        }
    cout<<ans;
    return 0;
}




//细胞个数
#include<iostream>
using namespace std;
bool a[110][110];
int n,m,ans;
char c;
int dfs(int x,int y){

    if(a[x][y]){
        a[x][y]=false;
        dfs(x-1,y);
        dfs(x,y-1);
        dfs(x+1,y);
        dfs(x,y+1);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c;
            if(c=='0'){
                a[i][j]=false;
            }else{
                a[i][j]=true;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]){
                dfs(i,j);
                ans++;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[101][101];
int ans;
void dfs(int x,int y)
{
    if(x<1||x>n||y<1||y>m||a[x][y]=='0') return;
    a[x][y]='0';
    dfs(x+1,y);
    dfs(x,y+1);
    dfs(x-1,y);
    dfs(x,y-1);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]!='0'){
                ans++;    dfs(i,j);
            }

        } 
    }
    cout<<ans;
    return 0;
}

树状数组（单点修改，区间修改等）

2023-08-15 09:13:10 By Cinque Terre wlc

树状数组有什么用

原版博客传送门

这里以前缀和为例，树状数组一般用于以下情景：

进行很多次操作：

1.修改某个节点的值 或 查询某一个区间的和。（单点修改，区间查询）

2.某一个区间同时加上某个值 或 查询某个节点修改后的值。（区间修改，单点查询）

3.某一个区间同时加上某个值 或 查询某一个区间的和。（区间修改，区间查询）

树状数组代码简单，效率优秀，空间占用低。事实上，树状数组不止局限于求前缀和，也支持求某一个区间的最值、求逆序对等问题。树状数组的其他问题这里不进行讨论（太多了写不完），这里只以求前缀和为问题切入点。

前置知识：

1.lowbit函数

关于lowbit函数是什么，链接贴上了，这里不多讲。为什么要用lowbit待会儿讲。

关于lowbit函数_issey的博客-CSDN博客

2. 前缀和

直接用例子来说明吧： 有一个数组a[10] = \left \{ 1,2,3,4,5,6,7,8,9,10 \right \}

那么它的前缀数组sum[10] = \left \{ 1,3,6,10,15,21,28,36,45,55\right \},计算公式:sum[i] = sum[i-1]+a[i]。

通过这个数组，可以快速求得a数组区间[l,r]的和，计算公式:sum_{l-r} = sum[r]-sum[l-1]

第一种：单点修改，区间查询

这是最简单的一种，也是树状数组最基本的功能。

树状数组，就是将数组化为树的形式，通过层层“管理”来维护前缀和，图中C1~C8就是一个个"管理",所在层数就是"管辖层级"，它下面那些层中，和它直接或间接相连的节点就是它的"管辖节点",如果往上没有管理的节点，则称该节点为"最高级管理"。

（注：从别的博客拷贝的，侵权立删）

我们修改树状数组的单个节点值时，需要将他们上面的"管理"节点也依次更新，查询前缀和时，需要查询范围内每一个“最高级管理”节点保存的前缀和累加。一定要注意：更新数据和查询前缀和时依次经过的"管理"节点是不同的，（尽管公式上他俩差不多）

1.（单点更新）维护树状数组时经过节点的规则：下标每次加了个二进制的低位1（不知道啥是低位1的自行转lowbit）：

例如：（二进制）1\rightarrow10\rightarrow100\rightarrow1000

(二进制) 1001\rightarrow1010\rightarrow1100\rightarrow10000

(二进制)101\rightarrow110\rightarrow1000\rightarrow10000

2. 查询前缀和经过节点的规则：下标每次减去一个二进制的低位1：

例如： （二进制）10000\rightarrow0

(二进制)111111\rightarrow111110\rightarrow111100\rightarrow111000\rightarrow110000\rightarrow100000\rightarrow0

又比如，看图里的那根蓝色的箭头(下标用二进制表示)，意思就是要求A_{01} - A_{111}的和,sum = sum_{111}+sum_{110}+sum_{100}

取低位1自然就是lowbit函数的作用。

再次说一下维护和查询的区别（以下下标均用二进制表示）

维护树状数组：意思是我们对某个节点加上（或减去）某个值后，它往上经过的节点均要更新。（它会影响往上沿路节点的值）

查询：查询1-i节点的和，比如我们要查询1-111111节点的和，把它依次减去最低位1的节点保存的前缀和加起来就是sum_{1-111111},即

sum=sum_{111111}+sum_{111110}+sum_{111100}+sum_{111000}+sum_{110000}+sum_{100000}

要注意查询时它在树中并不是"往下走"的，参考图中蓝色箭头，它的作用其实是把包括111111节点之前的各个"最高级管理员"保存的前缀和加起来。

好累，太难描述了。

接下来是[l,r]区间查询，例如查询100-100000节点的区间和，就是先求出1-100000的区间和，再求出1-11的区间和，然后两者相减即可。

sum_{l-r} = sum[r]-sum[l-1]

树状数组时间复杂度

单点修改：需要从底层往上依次更新节点，所以修改一次的复杂度为O(logn)，对比普通数组修改节点值的时间复杂度：O(n)。

区间查询：依次加上减去低位1的节点值，时间复杂度O(logn),对比普通求前缀和的时间复杂度:O(n).

总体时间复杂度:O(logn)

单点修改，区间查询模板题

第一种的各个函数就不分开写了，树状数组的板子都大同小异，放一个单点更新，区间求和的板子题，本来打算放个模板上来，结果发现7个月之前能过，现在再交居然T了，（离谱），板子干脆放后面两种写吧，后面两种会包括第一种的板子。

题目链接：Problem - 1166 (dingbacode.com) 敌兵布阵

第二种：区间修改，单点查询

前置知识：差分数组

差分，即数据之间的差，差分数组，即数组中每相邻两个数据之间的差组成的数组。

例如：有一个数组A[10] = [2,2,3,3,4,5,6,9,9,7]

那么A的差分数组B[10] = [2,0,1,0,1,1,1,3,0,-2],计算公式：B[0] = A[0],B[i] = A[i]-A[i-1].

那么B的前缀数组就是A数组对应的值。比如Bsum_{3} = A[3] = 3.

使用差分数组主要是为了区间修改，具体的说明可以去看这篇博客：

差分数组是个啥？能干啥？怎么用？（差分详解+例题）_From now on...的Blogs-CSDN博客_差分数组

了解了差分数组后，可以得到一个结论：当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的**右端点的后一个值则会相反地变化**，而其他点的值保持不变。

正题

充分了解了第一种树状数组之后，我们可以得知，树状数组的单点更新是相对麻烦的，如果要将某一个区间统一加上某个值，采用第一种方式，一次更新的时间复杂度会是O(mlogn),（m为区间长度）。

但是如果我们用差分数组来进行操作：

每次更新维护差分的树状数组d，查询单点的值时，根据前置知识，差分数组的前i个值的和就是原数组第i个值，即：

a_n = \sum_{i=1}^nd_i

所以查询差分的树状数组d的前缀和sum_{i}，就可以得到a_i。我们就可以将每次更新区间的时间复杂度从O(mlogn)降低至O(logn).

单点查询（查询某个点的值）相对简单，那么紧接着是第三种：

第三种：区间更新，区间查询

思路继承第二种，都是利用了差分思想，区间更新的步骤一样，不过区间查询，查询的是某一个区间的和。

通过第二种，我们得知差分数组B的前缀数组就是原数据A数组对应的值。接下来我们要求A数组[l,r]区间的和。又继承了第一种思路求[l,r]区间和的部分思路，我们应该先求[1,r]的和，再减去[1,l-1]的和。

直接来一手公式，第三种用公式反而更容易理解：

设A为原数组，D为A的差分数组，则有：

d_i = a_{i}-a_{i-1},d[0] =a[0]

即，

a_n = \sum_{i=1}^nd_i

而A的前缀数组为:\sum_{i=1}^xa_i，带入公式得：

\sum_{i=1}^xa_i = \sum_{i=1}^x\sum_{j=1}^id_i = \sum_{i=1}^x(x-i+1)d_i\\ =(x+1)\sum_{i=1}^xd_i-\sum_{i=1}^xid_i

这样一来我们要求区间和，只需要维护两个树状数组：d的前缀数组和id的前缀数组就行了，然后通过上面这个公式就可以直接求出来a的前缀和。

接下来是区间修改，区间查询的各个部分的代码（其实也包括了前两种的代码，更新和查询原理都是一样的）

获取最低位1：

//获取最低位1
int lowbit(int x){return x&(-x);}

下面的代码中，d的前缀数组名称为differ，id的前缀数组名称为idiffer。

区间修改：

//该模块功能：在[l,r]区间同时加上某个值value
void update(int idex,int value,int n)
{
    int i = idex;
    while(idex<=n){
        differ[idex] += (ll)value;
        idiffer[idex] += (ll)value*i;
        idex += lowbit(idex);
    }
}

//注意，区间修改根据差分数组的规则，要修改两次：
update(l,value,n);
update(r+1,-value,n);

区间查询：

//该模块功能：获取[l,r]区间的前缀和
ll getSum(int idex)
{
    ll sum = 0;
    int x = idex;
    while(idex){
        sum += (x+1)*differ[idex];
        sum -= idiffer[idex];
        idex -= lowbit(idex);
    }
    return sum;
}

//查询[l,r]区间要先查[1,r]的和，减去[1,l-1]的和
sum += getSum(i,r);
sum -= getSum(i,l-1);

最后，分享一道区间修改，区间查询的模板题，题解代码完全可以作为模板代码。

题目链接：saikr oj | 二进制

题解链接： ADPC2 B二进制题解_issey的博客-CSDN博客

【采药】题解-聊聊动态规划与记忆化搜索

2023-06-03 11:30:27 By Cinque Terre wlc

聊聊动态规划与记忆化搜索

(https://www.luogu.com.cn/blog/interestingLSY/memdfs-and-dp)

(https://www.luogu.com.cn/blog/kaiyuandeboke/dong-tai-gui-hua-yu-ji-yi-hua-sou-suo)

by $\color{Gray}{InterestingLSY}$ (菜到发灰) ，在此一并感谢 $\color{purple}{ComeIntoPower}$dalao的指点qwq

想体验把暴搜改改就是正解的快感吗? 想体验状压dp看似状态多到爆炸实际一跑却嗷嗷快(实际有效的状态数很少)的荣耀吗? 记忆化搜索,符合您的需求!只要998,记忆化搜索带回家!记忆化搜索,记忆化搜索,再说一遍,记忆化搜索!

先点个赞吧(逃

_由于我讲的比较磨叽,兜售目录一份,dalao们可以选择自己喜欢的部分看_

目录：

  • 记忆化搜索是啥

  • 记忆化搜索和动态规划有啥关系

  • 如何写记忆化搜索

  • 记忆化搜索的优缺点

  • 记忆化搜索的注意事项

  • 相关文章推荐

1. 记忆化搜索是啥（引入

好，就以 这道题 为例，我不会动态规划，只会搜索，我就会直接写一个粗暴的 DFS :

_注: 为了方便食用, 本文中所有代码省略头文件_

int n,t;
int tcost[103],mget[103];
int ans = 0;
void dfs( int pos , int tleft , int tans ){
    if( tleft &lt; 0 ) return;
    if( pos == n+1 ){
        ans = max(ans,tans);
        return;
    }
    dfs(pos+1,tleft,tans);
    dfs(pos+1,tleft-tcost[pos],tans+mget[pos]);
}
int main(){
    cin &gt;&gt; t &gt;&gt; n;
    for(int i = 1;i &lt;= n;i++)
        cin &gt;&gt; tcost[i] &gt;&gt; mget[i];
    dfs(1,t,0);
    cout &lt;&lt; ans &lt;&lt; endl;
    return 0;
}`</pre>

这就是个十分智障的大暴搜是吧......

emmmmmm....... $\color{Red}{30}$ 分

然后我心血来潮, 想不借助任何 &quot;外部变量&quot;(就是 dfs 函数外且 ** 值随 dfs 运行而改变的变量 **), 比如 ans

把 ans 删了之后就有一个问题: 我们拿什么来记录答案?

答案很简单:

** 返回值!**

此时 $dfs(pos,tleft)$ 返回在时间 $tleft$ 内采集 ** 后 **$pos$ 个草药, 能获得的最大收益

不理解就看看代码吧:

<pre>`int n,time;
int tcost[103],mget[103];
int dfs(int pos,int tleft){
    if(pos == n+1)
        return 0;
    int dfs1,dfs2 = -INF;
    dfs1 = dfs(pos+1,tleft);
    if( tleft &gt;= tcost[pos] )
        dfs2 = dfs(pos+1,tleft-tcost[pos]) + mget[pos];
    return max(dfs1,dfs2);
}
int main(){
    cin &gt;&gt; time &gt;&gt; n;
    for(int i = 1;i &lt;= n;i++)
        cin &gt;&gt; tcost[i] &gt;&gt; mget[i];
    cout &lt;&lt; dfs(1,time) &lt;&lt; endl;
    return 0;
}`</pre>

<del>emmmmmm....... 还是 $\color{Red}{30}$ 分</del>

但这个时候, 我们的程序已经不依赖任何外部变量了.

然后我非常无聊, 将所有 dfs 的返回值都记录下来, 竟然发现......

** 震惊, 对于相同的 pos 和 tleft,dfs 的返回值总是相同的!**

想一想也不奇怪, 因为我们的 dfs 没有依赖任何外部变量.

旁白: 像 $tcost[103]$,$mget[103]$ 这种东西不算是外部变量, 因为她们在 dfs 过程中不变.

然后?

开个数组 $mem$ , 记录下来每个 $dfs(pos,tleft)$ 的返回值. 刚开始把 $mem$ 中每个值都设成 $-1$ (代表没访问过). 每次刚刚进入一个 dfs 前(我们的 dfs 是递归调用的嘛), 都检测 $mem[pos][tleft]$ 是否为 $-1$ , 如果是就正常执行并把答案记录到 $mem$ 中, 否则?

** 直接返回 $mem$ 中的值!**

<pre>`int n,t;
int tcost[103],mget[103];
int mem[103][1003];
int dfs(int pos,int tleft){
    if( mem[pos][tleft] != -1 ) return mem[pos][tleft];
    if(pos == n+1)
        return mem[pos][tleft] = 0;
    int dfs1,dfs2 = -INF;
    dfs1 = dfs(pos+1,tleft);
    if( tleft &gt;= tcost[pos] )
        dfs2 = dfs(pos+1,tleft-tcost[pos]) + mget[pos];
    return mem[pos][tleft] = max(dfs1,dfs2);
}
int main(){
    memset(mem,-1,sizeof(mem));
    cin &gt;&gt; t &gt;&gt; n;
    for(int i = 1;i &lt;= n;i++)
        cin &gt;&gt; tcost[i] &gt;&gt; mget[i];
    cout &lt;&lt; dfs(1,t) &lt;&lt; endl;
    return 0;
}`</pre>

此时 $mem$ 的意义与 dfs 相同:

> 在时间 $tleft$ 内采集 **后** $pos$ 个草药, 能获得的最大收益

这能 ac?

能.** 这就是 &quot;采药&quot; 那题的 AC 代码 **

好我们 yy 出了记忆化搜索

#### 总结一下记忆化搜索是啥:
  • 不依赖任何 外部变量
  • 答案以返回值的形式存在, 而不能以参数的形式存在(就是不能将 dfs 定义成 $dfs(pos ,tleft , nowans )$, 这里面的 nowans 不符合要求).
  • 对于相同一组参数, dfs 返回值总是相同的
* * *

## 2. 记忆化搜索与动态规划的关系:（分析

<del>基本是朋 (ji) 友关系</del>

有人会问: 记忆化搜索难道不是搜索?

一定程度上来说，她是搜索.但个人认为她更像dp

**其实说白了，记忆化搜索就是dp**

不信你看$mem$ 的意义:

> 在时间 $tleft$ 内采集 **后** $pos$ 个草药, 能获得的最大收益

这不就是dp的状态?

由上面的代码中可以看出:

> $dfs(pos,left) = max(dfs(pos+1,tleft-tcost[pos])+mget[pos]\ ,\ dfs(pos+1,tleft)$

即为

> $mem[pos][tleft] = max(mem[pos+1][tleft-tcost[pos]]+mget[pos]\ ,\ mem[pos+1][tleft])$

这不就是dp的状态转移?

总结一下：

> 记忆化搜索和动态规划**从根本上来讲就是一个东西**,**(印象中)任何一个 dp 方程都能转为记忆化搜索 ，反之亦然（为什么？见下文“体现在”的第四条）

体现在
  • 根据记忆化搜索的参数可以直接得到dp的状态，反之亦然
  • 根据记忆化搜索的递归关系可以写出状态转移方程，这个方程可以直接写出循环式的dp，只不过是反的(想想为什么？)，反之亦然
  • 大部分记忆化搜索时空复杂度与 不加优化的 dp 完全相同

  • 最重要的一点：二者思想类似！！ 核心思想均为：利用对于相同参数答案相同的特性，对于相同的参数（循环式的dp体现为数组下标），记录其答案，免去重复计算，从而起到优化时间复杂度的作用。这，便是二者的精髓。**

    建议好好想想第四条。记住，学一个算法，一定要理解他的精髓。

    举个栗子:

    $dp[i][j][k] = dp[i+1][j+1][k-a[j]] + dp[i+1][j][k]$

    转为

    `int dfs( int i , int j , int k ){
    边界条件
    if( mem[i][j][k] != -1 ) return mem[i][j][k];
    return mem[i][j][k] = dfs(i+1,j+1,k-a[j]) + dfs(i+1,j,k);
}
int main(){
    memset(mem,-1,sizeof(mem));
    读入
    cout << dfs(1,0,0) << endl;
}`

    二者满足上面提到的所有关系

* * *

## 3. 如何写记忆化搜索

### 方法I（由动态规划开始思考）:
  1. 把这道题的dp状态和方程写出来
  2. 根据他们写出dfs函数

  3. 添加记忆化数组

    举例:

    $dp[i] = max\{dp[j]+1\}\quad 1 \leq j < i \text{且}a[j]<a[i]$ (最长上升子序列)

    转为

    `int dfs( int i ){

    if( mem[i] != -1 ) return mem[i];
int ret = 1;
for( int j = 1 ; j &lt; i ; j++ )
    if( a[j] &lt; a[i] )
        ret = max(ret,dfs(j)+1);
return mem[i] = ret;

    } int main(){

    memset(mem,-1,sizeof(mem));
读入
cout &lt;&lt; dfs(n) &lt;&lt; endl;

    }

方法II（由暴搜开始思考）:

  1. 写出这道题的暴搜程序(最好是dfs)
  2. 将这个dfs改成"无需外部变量"的dfs
  3. 添加记忆化数组

举例: 本文最开始介绍"什么是记忆化搜索"时举的"采药"那题的例子，就是典型的方法II

4. 记忆化搜索的优缺点

优点:

  • 记忆化搜索可以避免搜到无用状态, 特别是在有状态压缩时

    举例: 给你一个有向图(注意不是完全图),经过每条边都有花费,求从点1出发,经过每个点恰好一次后的最小花费(最后不用回到起点),保证路径存在.

dp状态很显然:

设 $dp[pos][mask]$ 表示身处在 $pos$ 处,走过 $mask$(mask为一个二进制数) 中的顶点后的最小花费

常规 $dp$ 的状态为 $O(n\cdot 2^n)$ , 转移复杂度(所有的加在一起)为 $O(m)$

但是!如果我们用记忆化搜索,就可以避免到很多无用的状态,比如 $pos$ 为起点却已经经过了 $>1$ 个点的情况.

然后就 $rk1$ 了

  • 不需要注意转移顺序(这里的"转移顺序"指正常dp中for循环的嵌套顺序以及循环变量是递增还是递减)

举例: 用常规 dp 写"合并石子"需要先枚举区间长度然后枚举起点,但记忆化搜索直接枚举断点(就是枚举当前区间由哪两个区间合并而成)然后递归下去就行

  • 边界情况非常好处理, 且能有效防止数组访问越界

  • 写起来简单易懂 至少我镇么认为 qwq

  • 有些 dp(如区间 dp)用记忆化搜索写很简单但正常 dp 很难

  • 记忆化搜索天生携带搜索天赋,可以使用技能"剪枝"!

缺点:

  • 致命伤: 不能滚动数组!(哪位 dalao 会记搜 + 滚动的请在评论区留名)

  • 有些优化比较难加

  • 由于递归, 有时效率较低但不至于 TLE (状压dp除外)

  • 代码有点长其实也不算太长

5. 记忆化搜索的注意事项

  • 千万别忘了加记忆化! (别笑, 认真的

  • 边界条件要加在检查当前数组值是否为 - 1 前(防止越界)

  • 数组不要开小了(逃

  • 在某些时候需要优化（如滚动数组、斜率优化时还是要用正常的dp

6. 相关文章推荐

《挑战程序设计竞赛》(又名白书)，对动态规划的引入的那一章（它也是从暴搜开始讲起）

wlc Avatar
中文 English

服务器时间: 2025-05-14 18:30:18 | 平邑一中官网