更新記錄
【1】2020.05.16-11:02
1.完善內容
正文
觀前提示
- 此文章為重溫系列，并不會講的很細致
- 需要有一定遞推遞回與搜索基礎
遞推
前言
雖說是遞推，但是它與動態規劃有著密不可分的關系
（我動態規劃連普及的水平都達不到）
所以說，遞推這東西最簡單，但又是初學者最難理解的東西
為什么說是簡單呢？
- 單獨拎出這個演算法來，你會發現你什么也講不了
為什么說難理解呢？
- 結合到題里面的時候，有時候你會發現你連思路都捋不出來
所以這里我們結合題目來講
斐波那契數列
定位：基礎題 / 入門難度
當然我這里指的裸題（你FFT+斐波那契數列出大問題）
\(f[i]=f[i-1]+f[i-2]\)
注意一下邊界條件
然后就沒了
沒啥可說的，注意到\(i-1\)和\(i-2\)都被求過，想到用陣列來存盤就可以了
#include<iostream>
using namespace std;
int a[1000100],num=0,in;
int main(){
a[1]=1;a[2]=1;cin>>num;
for(int i=3;i<1000002;i++)
a[i]=(a[i-1]+a[i-2])
for(int i=0;i<num;i++){
cin>>in;cout<<a[in]<<"\n";
}
}
位數問題
定位：基礎題 / 普及-難度
這道題做起來依然很簡單，只不過程序有點考驗大家
兩位數中，帶有奇數個3的是：
\(13,23,43,53,63,73,83,93\)
\(30,31,32,34,35,36,37,38,39\)
那么我們觀察發現：當3不在最高位的時候，數量乘8
- 高位不能為0或3
在最高位的時候數量乘9
- 不是最高位的時候可以為0但不能為3
依此類推，三位數中含有奇數個3的數的數量為：
- 個位
\((103,113,123,143,153,163,173,183,193)\)
共9×8=72個 - 十位
\((130,131,132,134,135,136,137,138,139)\)
共9×8=72個 - 百位
\((301,302,304,305,306...398,399)\)
共100-9-9=81個 - 其他
\((333)\)
共1個
所以含有奇數個3的數的數量為：72×2+81+1=226個
定義陣列\(f[i][2]\)：
- \(f[i][0]\)表示i位數中含有偶數個3的數的數量
- \(f[i][1]\)表示i位數中含有奇數個3的數的數量
動態轉移方程為：
\(f[i][0]=(f[i-1][0]*9+f[i-1][1])%12345\)
\(f[i][1]=(f[i-1][1]*9+f[i-1][0])%12345\)
注意最高位單獨乘8就可以了
#include<iostream>
using namespace std;
int f[20001][2],n;
int main(){
cin>>n;f[1][0]=9;f[1][1]=1;
for(int i=2;i<n;i++){
f[i][0]=(f[i-1][0]*9+f[i-1][1])%12345;
f[i][1]=(f[i-1][1]*9+f[i-1][0])%12345;
}
if(n!=1){
f[n][0]=f[n-1][0]*8+f[n-1][1];
f[n][1]=f[n-1][1]*8+f[n-1][0];
}
cout<<f[n][0]%12345;
}
踩方格
定位：練習題 / 普及難度
這個題的代碼量真的是非常少，但是這個思路的話還是不太好想
很多人都被這不能再走第二次迷惑了
但是我們只需要分開方向掃一遍即可
定義\(f[i][3]\)
- \(f[i][0]\)表示第i步向上走
- \(f[i][1]\)表示第i步向左走
- \(f[i][2]\)表示第i步向右走
#include<iostream>
using namespace std;
int n,f[25][3];
int main(){
cin>>n;f[1][0]=1;f[1][1]=1;f[1][2]=1;
for(int i=2;i<=n;i++){
f[i][0]=f[i-1][0]+f[i-1][1]+f[i-1][2];
f[i][1]=f[i-1][0]+f[i-1][1];
f[i][2]=f[i-1][0]+f[i-1][2];
}
cout<<f[n][0]+f[n][1]+f[n][2];
//最后加起來就是答案
}
山區建小學
定位：思考題 / 提高難度
這道題考察的比較全面，就其中的動規來說，代碼很少但是比較難想出來
定義\(b[i][o]\)與\(f[i][o]\)
\(b[i][o]\)表示i到o如果建一所小學的話，i到o上所有的村莊到這所小學的距離和
\(f[i][o]\)表示前i個村莊修o所小學的最優解
#include<iostream>
#include<cmath>
using namespace std;
int n,m,a[501],mid,i,o,p;
int b[501][501],f[501][501];
int main(){
cin>>n>>m;
for(i=2;i<=n;i++){
cin>>a[i];a[i]+=a[i-1];
}
//這里用前綴和用來求兩點間距離
for(i=1;i<=n;i++){
for(o=i;o<=n;o++){
mid=(i+o)/2;
for(p=i;p<=o;p++)
b[i][o]+=abs(a[mid]-a[p]);
}
}
//顯然，兩點之間的中點一定是b[i][o]的最小值
for(int i=0;i<=n;i++){
for(int o=0;o<=m;o++)
f[i][o]=99999999;
}
//初始化
f[0][0]=0;
for(i=1;i<=n;i++){
for(o=1;o<=m;o++){
if(o>i){
f[i][o]=0;continue;
}
//要修的學校比村莊數還多=>每個村莊家門口就有小學=>距離和為零
for(p=o-1;p<i;p++)
f[i][o]=min(f[i][o],f[p][o-1]+b[p+1][i]);
//對前i個村莊列舉
}
}
cout<<f[n][m];
//輸出
}
遞回
其實遞回可以理解為動規的另一種寫法（只不過更慢，占記憶體更多就是了）
數的計數
定位：基礎題 / 普及-難度
這道題就是一道（反遞回）送經驗題
遞回思路：左邊從1開始添加到n/2
添加完畢后進行下一步的遞回
遞回版本超時1毫秒
#include<cstdio>
int n,num=1;
inline void pan(int n){
for(int i=1;i<=(n>>1);++i){
num+=1;pan(i);
}
}
int main(){
scanf("%d",&n);
pan(n);
printf("%d",num);
}
超時可不太好，所以我們換成動規
從1掃到n就可以了
小小的證明：
- n左邊只能添加比起小一半的數
- 但是這個添加的數（因為比n小）我們之前計算過了
- 直接加上就好
- 注意邊界條件
換成動規就完美AC了
#include<iostream>
using namespace std;
long long int f[1002];int a;
int main()
{
f[1]=1;
for(int i=2;i<=1001;i++){
for(int o=1;o<=i/2;o++)
f[i]+=f[o];
f[i]+=1;
}
cin>>a;cout<<f[a];
}
所以說還是能用動規就用動規，遞推TLE和MLE讓你玩不起
搜索
（這個演算法最大的貢獻就是證明了遞回并不是一無是處）
通俗來講就是我們在一個決策點上會遇到許多不同的情況
選擇一種之后又會有許多不同的情況
但存在邊界并且決策點有限
于是暴力遞回————搜索演算法就出現了！！
搜索，就是把所有情況都遍歷一遍
不過時間與記憶體什么的都會很高
有時候還會用到回溯，剪枝（區間動規）等一系列玄學操作
馬走日
定位：基礎題 / 普及難度
沒啥說的，每到一步擴展就行了
#include<iostream>
using namespace std;
int t,n,m,x,y,num;
bool bl[101][101];
int sx[8]={2,1,-1,-2,2,1,-1,-2};
int sy[8]={1,2,2,1,-1,-2,-2,-1};
void pan(int x,int y,int s){
if(x<0||y<0||x>=n||y>=m) return;
if(s==n*m) num+=1;
bl[x][y]=1;
//進行下一步時暫時標記這個點用過
for(int i=0;i<8;i++)
if(!bl[x+sx[i]][y+sy[i]])
pan(x+sx[i],y+sy[i],s+1);
//核心，向8個方向擴展
bl[x][y]=0;
//這一步搜索完了，標記沒用過
}
int main(){
cin>>t;
for(int i=0;i<t;i++){
num=0;cin>>n>>m>>x>>y;
pan(x,y,1);cout<<num<<"\n";
}
}
單詞接龍
定位：練習題 / 普及難度
整理題目可得：
-
一個單詞最多用兩次
-
單詞可以不全用完
-
不可以包含
-
重疊部分應該越少越好
所以說實作一個判斷重疊部分長度的函式
搜一遍即可
#include<iostream>
using namespace std;
string a[50];
int n,cnt[50],num,maxn;
char begin;
int yn(int a,int b){
int ayn=1,al=(::a[a].length());
for(int i=al-1;i>=0;i--){
ayn=1;
if((::a[a][i])==(::a[b][0])){
for(int o=i;o<al;o++){
if((::a[a][o])!=(::a[b][o-i])){
ayn=0;break;
}
}
if(ayn)
return al-i;
}
}
return 0;
}
void fs(int wei,int l,int p){
if(l>maxn)
maxn=l;
for(int i=0;i<n;i++){
if(cnt[i]>=2) continue;
int c=yn(wei,i);
if(c&&(c!=a[wei].length()||c!=a[i].length())){
cnt[i]+=1;fs(i,l+a[i].length()-c,p+1);cnt[i]-=1;
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>begin;
for(int i=0;i<n;i++){
if(a[i][0]==begin){
cnt[i]+=1;fs(i,a[i].length(),1);cnt[i]-=1;
}
}
cout<<maxn;
}
總結
- 這三個演算法相互聯系，學習時注意均衡
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/51521.html
標籤：其他
上一篇：位運算