Logo wlc的博客

博客

标签
个人博客 poj p5 题解 p1831 记忆化搜索 dp 树状数组

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. 相关文章推荐

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

【p1831题解】摆花

2023-05-13 21:22:15 By Cinque Terre wlc

题目传送门

题意

题目大意： 放 $m盆花在一排，总共有 $n种花，编号为 $i的花最多能放 $a[$i]盆，摆放时同一种花要放一起，且花的编号要从小到大。

思路：

解析

一、暴力

直接暴力搜索得到结果，骗30分。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 105;
const int mod = 1e6 + 7;
LL n, m, a[N];
LL dfs(int k, int p){    //k为第几种花，p为几盆花 
    if (p == m) return 1;
    if (k > n || p > m) return 0;
    LL ans = 0;
    for (int i = 0; i <= a[k]; i++)
        ans = (ans + dfs(k + 1, p + i)) % mod;
    return ans;
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    cout << dfs(1, 0) << "\n";
    return 0;
}

二、记忆化搜索

暴力超时，于是想到通过记忆化减少时间，100分。


#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 105;
const int mod = 1e6 + 7;
LL n, m, num[N][N], a[N];
LL dfs(int k, int p){    //k为第几种花，p为几盆花 
    if (p == m) return 1;
    if (k > n || p > m) return 0;
    if (num[k][p]) return num[k][p];
    LL ans = 0;
    for (int i = 0; i <= a[k]; i++)
        ans = (ans + dfs(k + 1, p + i)) % mod;
    num[k][p] = ans;
    return ans;
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    cout << dfs(1, 0) << "\n";
    return 0;
}

三、dp


#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1e6 + 7;
const int N = 105;
LL n, m, f[N][N], a[N];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= a[i]; k++)
                if (j >= k)
                    f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
    cout << f[n][m] % mod << "\n";
    return 0;
}

POJ题目分类推荐 （很好很有层次感）

2023-05-13 21:11:00 By Cinque Terre wlc

OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

初级:

一.基本算法:

 (1)枚举. (poj1753,poj2965) 
 (2)贪心(poj1328,poj2109,poj2586) 
 (3)递归和分治法. 
 (4)递推. 
 (5)构造法.(poj3295) 
 (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

(1)图的深度优先遍历和广度优先遍历. 
 (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) 
    (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) 
 (3)最小生成树算法(prim,kruskal) 
    (poj1789,poj2485,poj1258,poj3026) 
 (4)拓扑排序 (poj1094) 
 (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) 
 (6)最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

 (1)串 (poj1035,poj3080,poj1936) 
 (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) 
 (3)简单并查集的应用. 
 (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)    
    (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) 
 (5)哈夫曼树(poj3253) 
 (6)堆 
 (7)trie树(静态建树、动态建树) (poj2513)

四.简单搜索

 (1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251) 
 (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) 
 (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

 (1)背包问题. (poj1837,poj1276) 
 (2)型如下表的简单DP(可参考lrj的书 page149): 
   1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 
   2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) 

     (poj3176,poj1080,poj1159) 
   3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)

六.数学

 (1)组合数学: 
    1.加法原理和乘法原理. 
    2.排列组合. 
    3.递推关系. 
      (POJ3252,poj1850,poj1019,poj1942) 
 (2)数论. 
    1.素数与整除问题 
    2.进制位. 
    3.同余模运算. 
      (poj2635, poj3292,poj1845,poj2115) 
 (3)计算方法. 
    1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)

七.计算几何学.

 (1)几何公式. 
 (2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

 (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) 
     (poj1408,poj1584) 
 (4)凸包. (poj2187,poj1113)

中级:

一.基本算法:

 (1)C++的标准模版库的应用. (poj3096,poj3007) 
 (2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

 (1)差分约束系统的建立和求解. (poj1201,poj2983) 
 (2)最小费用最大流(poj2516,poj2195) 
 (3)双连通分量(poj2942) 
 (4)强连通分支及其缩点.(poj2186) 
 (5)图的割边和割点(poj3352) 
 (6)最小割模型、网络流规约(poj3308, )

三.数据结构.

 (1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750) 
 (2)静态二叉检索树. (poj2482,poj2352) 
 (3)树状树组(poj1195,poj3321) 
 (4)RMQ. (poj3264,poj3368) 
 (5)并查集的高级应用. (poj1703,2492) 
 (6)KMP算法. (poj1961,poj2406)

四.搜索

 (1)最优化剪枝和可行性剪枝 
 (2)搜索的技巧和优化 (poj3411,poj1724) 
 (3)记忆化搜索(poj3373,poj1691)

五.动态规划

 (1)较为复杂的动态规划(如动态规划解特别的施行商问题等) 
     (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034) 
 (2)记录状态的动态规划. (POJ3254,poj2411,poj1185) 
 (3)树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

 (1)组合数学: 
    1.容斥原理. 
    2.抽屉原理. 
    3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026). 
    4.递推关系和母函数.        
 (2)数学. 
    1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222) 
    2.概率问题. (poj3071,poj3440) 
    3.GCD、扩展的欧几里德(中国剩余定理) (poj3101) 
 (3)计算方法. 
    1.0/1分数规划. (poj2976) 
    2.三分法求解单峰(单谷)的极值. 
    3.矩阵法(poj3150,poj3422,poj3070) 
    4.迭代逼近(poj3301) 
 (4)随机化算法(poj3318,poj2454) 
 (5)杂题. 
     (poj1870,poj3296,poj3286,poj1095)

七.计算几何学.

    (1)坐标离散化. 
    (2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用). 
        (poj1765,poj1177,poj1151,poj3277,poj2280,poj3004) 
    (3)多边形的内核(半平面交)(poj3130,poj3335) 
    (4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429

)

高级:

一.基本算法要求:

  (1)代码快速写成,精简但不失风格   
      (poj2525,poj1684,poj1421,poj1048,poj2050,poj3306) 
  (2)保证正确性和高效性. poj3434

二.图算法:

  (1)度限制最小生成树和第K最短路. (poj1639) 
  (2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)

     (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446 
  (3)最优比率生成树. (poj2728) 
  (4)最小树形图(poj3164) 
  (5)次小生成树. 
  (6)无向图、有向图的最小环

三.数据结构.

  (1)trie图的建立和应用. (poj2778) 
  (2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
      (RMQ+dfs)).(poj1330) 
  (3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的 目的). (poj2823) 
  (4)左偏树(可合并堆).   
  (5)后缀树(非常有用的数据结构,也是赛区考题的热点). 
     (poj3415,poj3294)

四.搜索

  (1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

  (2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储

状态、双向广搜、A算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482) (3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大 、可以考虑双向搜索或者是轮换搜索、IDA算法. (poj3131,poj2870,poj2286)

五.动态规划

  (1)需要用数据结构优化的动态规划. 
     (poj2754,poj3378,poj3017) 
  (2)四边形不等式理论. 
  (3)较难的状态DP(poj3133)

六.数学

  (1)组合数学. 
    1.MoBius反演(poj2888,poj2154) 
    2.偏序关系理论. 
  (2)博奕论. 
    1.极大极小过程(poj3317,poj1085) 
    2.Nim问题.

七.计算几何学.

  (1)半平面求交(poj3384,poj2540) 
  (2)可视图的建立(poj2966) 
  (3)点集最小圆覆盖. 
  (4)对踵点(poj2079) 
  八.综合题. 
  (poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263

)

关于推迟2022年CSP-JS第二轮和NOIP举办时间的通知

2022-09-17 09:54:20 By Cinque Terre wlc

OJ填写真实姓名

2022-09-16 19:01:11 By Cinque Terre wlc

pyyzoj上还有部分同学没有填写学校和真实姓名，请这些同学给我博客留言，我在后台帮大家改下！ 比如 账号：wlc 学校：平邑一中 真实姓名：王立才

请这些同学给我博客留言！

OJ增加注册审核、密码找回功能

2022-04-11 00:35:18 By Cinque Terre wlc

【背景】

自PYYZOJ上线以来，题库题目越来越多，同学们学习情绪日益高涨！

虽然疫情封校但是挡不住OIer 们学习的热情，为了使OJ平台更加健康的运行，增加注册审核和密码找回功能。

【使用方法】

1.注册审核

访问注册页面，填写资料注册新用户，管理员审核通过后才能正常使用。

2.密码找回

如您忘记密码不能正常登录OJ，在登录页面增加了密码找回功能。

点击找回密码，填好您的用户名后，系统会给您邮箱发送密码重置的邮件，点击邮件的链接地址重新填写新密码即可。

共 12 篇博客
中文 English

Server Time: 2025-05-14 21:56:57 | ShanDong PingYi Middle school