NIKOLA

題目大意：

NIKOLA畫了一排數字，他一開始在1，他可以往前跳T+1格（T為上一次跳到此格跳的格數），或往后T格（T一開始為0），但不能跳出界，沒跳到一個格子，就要加上此格子的值（一開始在第一個的時候不用，但從前面跳回第一格時要），問跳到第n格所得的值最小是多少

樣例輸入

6
1
2
3
4
5
6

樣例輸出

12

數據范圍限制

2≤N≤1000
每個格子的值是一個正整數，絕對不超過500

樣例解釋：

先從第一格跳到第二格（2），再從第二格跳到第一格（1），再從第一格跳到第三格（3），最后從第三格跳到第六格（6），所以結果是2+1+3+6=12

解題思路：

這道題本蒟蒻用了兩種方法做：記憶化搜索和DP

記憶化搜索(dfs加剪枝)：

我們用dfs(x,sum,d)來代表跳到x所得值為sum，上一次跳到這里跳了d格，然后用b[x][d]來表示上一個點跳了d步跳到x的最小值，每一次dfs時，判斷sum是否大于b[x][d]如果大于，就退出，否則代替b[x][d]，還要判斷sum是否大于ans（當前最小結果），如果大于也要退出

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int ans,n,a[1005],b[1005][1005]; void dfs(int x,int sum,int d) {if (x==n)//判斷是否為結果{ans=min(ans,sum);//求最小值return;//退出}if (sum>ans) return;//判斷是否大于if (sum>=b[x][d]) return;//判斷是否更優b[x][d]=sum;//代替if (x>d) dfs(x-d,sum+a[x-d],d);//判斷是否越界，如果沒有就可以往后，跳到了x-d就要加上他的值if (x+d+1<=n) dfs(x+d+1,sum+a[x+d+1],d+1);//沒越界就可以往前 } int main() {scanf("%d",&n);for (int i=1;i<=n;++i)scanf("%d",&a[i]);memset(b,127/3,sizeof(b));//預處理ans=2147483647;//預處理b[1][0]=0;//初始位置dfs(2,a[2],1);//dfsprintf("%d",ans); //輸出結果 }

DP：

我用f[i][j]來表示上一步跳了i步跳到了j點的最小花費,就得出了動態轉移方程：

$$f[i][j]=min\{\begin{array}{c}f[i?1][j?i]+a[j]\\ f[i][j+i]+a[j]\end{array}$$

注釋：

上面的是從后面往前跳，下面的是從前面往后跳

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,ans,a[1005],f[1005][1005]; int main() {scanf("%d",&n);for (int i=1;i<=n;++i)scanf("%d",&a[i]);memset(f,127/3,sizeof(f));//預處理f[0][1]=0;//第一個位置ans=2147483647;//預處理for (int i=1;i<=n;++i)//步數{for (int j=n;j>0;--j)//正著的話會無法前面往后跳f[i][j]=min(f[i][j+i]+a[j],f[i-1][j-i]+a[j]);//動態轉移方程ans=min(ans,f[i][n]);//求最小的}printf("%d",ans);//輸出 }

總結

以上是生活随笔為你收集整理的【DP】【记忆化搜索】NIKOLA（jzoj 1150）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。