《深入浅出算法竞赛》-递推与递归(笔记版）

深入浅出真的适合入门，感觉4+看不懂的题解多半是基础没打牢，直接从深入浅出回炉重造吧;

#include<bits/stdc++.h>using namespace std;
int n;
const int N=5e3+10;
int f[N];signed main()
{cin>>n;f[1]=1,f[2]=2;for(int i=3;i<=n;i++){f[i]=f[i-2]+f[i-1];}cout<<f[n]<<endl;return 0;
}

怎么才50分

开longlong 老铁

#include<bits/stdc++.h>using namespace std;
#define int long long 
int n;
const int N=5e3+10;
int f[N];signed main()
{cin>>n;f[1]=1,f[2]=2;for(int i=3;i<=n;i++){f[i]=f[i-2]+f[i-1];}cout<<f[n]<<endl;return 0;
}

才60分

别想了，要用高精度，关于为什么需要高精度

#include<bits/stdc++.h>using namespace std;
#define int long long 
int n;
const int N=5e3+10;
int a[N],b[N],c[N];
//a,b用来存加数，c用来存各位相加结果，以判断是否要进位
int ns=1;
// ns用来计数signed main()
{cin>>n;if(n<3){cout<<n<<endl;return 0;}a[1]=1,b[1]=2;for(int i=3;i<=n;i++){for(int j=1;j<=n;j++) c[j]=a[j]+b[j];for(int j=1;j<=ns;j++){if(c[j]>9){c[j+1]+=c[j]/10;c[j]%=10;if(j+1>ns) ns++;}}for(int j=1;j<=ns;j++) a[j]=b[j];for(int j=1;j<=ns;j++) b[j]=c[j];}for(int i=ns;i>=1;i--) cout<<c[i];return 0;
}

需要掌握的高精度加法，a,b,c手算模拟竖式，算完一次数字做交换，变成新的两个加数，知道得到目标值。

“标数法”第一次听——dp题解

#include<bits/stdc++.h>using namespace std;
const int N=25;
//要开long long 
typedef long long ll;
int ctrl[N][N];
int dx[]={0,-2,-1,1,2,2,1,-1,-2};
int dy[]={0,1,2,2,1,-1,-2,-2,-1};
ll f[N][N];signed main()
{int n,m,mx,my;cin>>n>>m>>mx>>my;for(int i=0;i<=8;i++){int x=mx+dx[i],y=my+dy[i];if(x<0||x>n||y<0||y>m) continue;ctrl[x][y]=1;}f[0][0]=1-ctrl[0][0];//f[0][1]=1,f[1][0]=1;for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){if(ctrl[i][j]) continue;if(i) f[i][j]+=f[i-1][j];if(j) f[i][j]+=f[i][j-1];}}cout<<f[n][m]<<endl;return 0;
}

栈和递推有什么关系

哦，大概知晓了，给定n个数，求出栈序的个数

讲得很好的一篇——递归+记忆化搜索和dp+递推

正所谓经典咏流传，推！

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=20;
ll f[N][N];
//i表示队列里的数，j表示栈中准备出栈的数ll dfs(int i,int j)
{if(f[i][j]) return f[i][j];if(i==0) return 1;if(j==0) return f[i][j]+=f[i-1][j+1];return f[i][j]+=f[i][j-1]+f[i-1][j+1];
}signed main()
{ll n;cin>>n;//一开始所有的数都在队列里dfs(n,0);cout<<f[0][0]<<endl;return 0;
}

dfs参数卡了一下，既然是记忆化数组，必少不了 i,j ，那要怎么穿实参呢

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=20;
ll f[N][N];
//i表示队列里的数，j表示栈中的数的个数ll dfs(int i,int j)
{if(f[i][j]) return f[i][j];if(i==0) return 1;if(j>0) f[i][j]+=dfs(i,j-1);//dfs不断分解成子问题，f[i][j]+=合并子问题到当前f[i][j]+=dfs(i-1,j+1);return f[i][j];//返回当前得到的最有子结构解
}signed main()
{ll n;cin>>n;//一开始所有的数都在队列里for()cout<<dfs(n,0)<<endl;return 0;
}

水过啦～

那就再来水一篇递推法

dfs到dp比较好的理解

但是递归和递推式就没什么关系了，状态定义都不一样了

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=20;
ll f[N][N];
//f[i][j] 表示当 i 个数入栈，j 个数出栈的时候，所拥有的最大方案数。signed main()
{int n;cin>>n;for(int i=1;i<=n;i++) f[i][0]=1; for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){//这是一句废话可以说，//if(i==1) f[i][j]+=f[i][j-1]; //如果入栈的数为一，那么当前方案由前一个状态的出栈元素决定；if(i==j) f[i][j]+=f[i][j-1]; //如果入栈和出栈的个数相等，此时栈中就为空，显然只能由前一个状态出栈一个，不可能是入栈还出现栈空的情况，因为先有钱才有出签，先入栈才能出栈f[i][j]=f[i-1][j]+f[i][j-1];}}cout<<f[n][n]<<endl;return 0;
}

第二种状态表示的dp，用到了卡特兰数，卡特兰先生研究出的有用的东西，理解《深入浅出》有个图

#include<bits/stdc++.h>using namespace std;
const int N=20;
typedef long long ll;
ll f[N];signed main()
{int n;cin>>n;f[0]=f[1]=1;for(int i=2;i<=n;i++){//第二层循环是计算f[i]的方案for(int j=0;j<i;j++){f[i]+=f[j]*f[i-j-1];}}cout<<f[n]<<endl;return 0;
}

先写一个递归的吧

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e3+10;
ll f[N];ll dfs(int x)
{if(f[x]!=-1) return f[x];// ans初始化为1，代表本身也是一个方案；ll ans=1;for(int i=1;i<=x/2;i++){ans+=dfs(i);}return f[x]=ans;
}signed main()
{int n;cin>>n;memset(f,-1,sizeof f);f[1]=1;cout<<dfs(n)<<endl;return 0;
}

再来一个递推式解法

#include<bits/stdc++.h>using namespace std;
const int N=1e3+10;
typedef long long ll;
ll f[N];signed main()
{int n;cin>>n;f[0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=i/2;j++){if(!f[j]) f[i]+=f[]}}return 0;
}

因为收到卡兰特数的那道题的启发，想用第二层循环去计算穷尽i这个数结尾之后可以➕多少个数，因为他是从1开始的，所以是一定能有前一个状态推出后一个状态的,然而我没有坚持写下去

#include<bits/stdc++.h>using namespace std;
const int N=1e3+10;
typedef long long ll;
ll f[N];signed main()
{int n;cin>>n;f[0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=i/2;j++){if(!f[j]) f[i]+=f[j];}f[i]++;}cout<<f[n]<<endl;return 0;
}

注释版

因为小于，n/2之后的数都可以，像f[4] 就会累加f[2]的方案数，所以从j=1开始累加到i/2，会得到最终的总方案数

#include<bits/stdc++.h>using namespace std;
const int N=1e3+10;
typedef long long ll;
ll f[N];signed main()
{int n;cin>>n;for(int i=1;i<=n;i++){//printf("f[%d] ",i);for(int j=1;j<=i/2;j++){//if(!f[j]) f[i]+=f[j];//printf("f[%d] ",j);}//cout<<endl;f[i]++;}cout<<f[n]<<endl;return 0;
}//f[7]=f[3]+f[1];

考的是递归

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
map<int,int> f;ll function(ll a, ll b, ll c)
{if(a<=0||b<=0||c<=0) return f[a][b][c]=1;}signed main()
{ll a,b,c;while(cin>>a>>b>>c){if(a==b&&b==c&&c==-1) break;ll ans = function(a,b,c);printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,ans);}return 0;
}

好奇怪，为什么输入会爆int，我之前直接开三维的int直接爆了，我还在想怎么用tuple存三元组,诶呦woc，因为大于20就就返回w(20,20,20);

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=60;
int f[N][N][N];int w(ll a, ll b, ll c)
{//这个放首位也会爆if(f[a][b][c]) return f[a][b][c];//这里也是if(a<=0||b<=0||c<=0) return f[a][b][c]=1;//这里返回会爆Nif(a>20||b>20||c>20) return f[a][b][c]=w(20,20,20);if(a<b&&b<c) return f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);return f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
}signed main()
{ll a,b,c;while(scanf("%lld%lld%lld",&a,&b,&c)){memset(f,0,sizeof f);if(a==b&&b==c&&c==-1) break;ll ans = w(a,b,c);printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,ans);}return 0;
}

正确的记忆化

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=60;
int f[N][N][N];int w(ll a, ll b, ll c)
{//这里也是if(a<=0||b<=0||c<=0) return 1;//这里返回会爆Nif(a>20||b>20||c>20) return w(20,20,20);if(f[a][b][c]) return f[a][b][c];if(a<b&&b<c) return f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);return f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
}signed main()
{ll a,b,c;while(scanf("%lld%lld%lld",&a,&b,&c)){//memset会超时//memset(f,0,sizeof f);if(a==b&&b==c&&c==-1) break;ll ans = w(a,b,c);printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,ans);}return 0;
}

告诉我压缩规则之后，叫我根据给出的压缩字符串推出原串

嘶，有点难顶

首要解决的问题，如何递归解开方括号？

#include<bits/stdc++.h>using namespace std;string expand()
{string s="",X;char c; int D;while(cin>>c){if(c=='['){cin>>D;X=expand();while(D--){s+=X;}}else if(c==']')return s;else s+=c;}return s;
}signed main()
{cout<<expand()<<endl;return 0;
}

读完数字应该在哪里expand呢

#include<bits/stdc++.h>using namespace std;string expand()
{string s="",X;char c;int D;while(cin>>c){if(c=='['){cin>>D;X=expand();while(D--){s+=X;}}else if(c==']'){return s;}else{s+=c;}}return s;
}signed main()
{cout<<expand()<<endl;return 0;
}

感觉复习加上掌握需要5个小时一章，还没算上课后习题的叻