題目鏈接：點擊查看

題目大意：給定n個點，以及m的最大體力值，共有三個狀態(tài)通過每個點

快速模式：消耗時間t1，消耗體力f1

勻速模式：消耗時間t2

慢速模式：消耗時間t3，恢復體力f2

問：通過n個點后所使用的最少時間。

這個題目的題意簡潔明了，轉(zhuǎn)移方程也很容易寫出：

dp初始化為inf，dp[0][m]=0;

dp[i][j]=min(dp[i-1][j-f1]+t1,dp[i-1][j]+t2,dp[i-1][j+f2]+t3);

共有兩種方式可以實現(xiàn)，即從前往后的遞推，和從后往前的記憶化搜索

記憶化搜索更簡單，但時間復雜度比遞推高了幾個常數(shù)等級

相對的遞推雖然復雜一點，但時間復雜度低

但在此題目無影響，都是0ms通過，上代碼：

遞推：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=150;int f1[N],f2[N],t1[N],t2[N],t3[N];int dp[N][N];int n,m;int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",t1+i,t2+i,t3+i,f1+i,f2+i);memset(dp,inf,sizeof(dp));dp[0][m]=0;for(int i=1;i<=n;i++)for(int j=0;j<=m;j++){if(j>=f1[i])dp[i][j-f1[i]]=min(dp[i-1][j]+t1[i],dp[i][j-f1[i]]);dp[i][j]=min(dp[i-1][j]+t2[i],dp[i][j]);if(j+f2[i]<m)dp[i][j+f2[i]]=min(dp[i][j+f2[i]],dp[i-1][j]+t3[i]);elsedp[i][m]=min(dp[i][m],dp[i-1][j]+t3[i]);}int mmin=inf;for(int i=0;i<=m;i++)mmin=min(mmin,dp[n][i]);cout<<mmin<<endl;}return 0; }

記憶化搜索：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=150;int f1[N],f2[N],t1[N],t2[N],t3[N];int dp[N][N];int n,m;int dfs(int t,int f) {if(t==1){if(f>=f1[1])return min(t1[1],min(t2[1],t3[1]));elsereturn min(t2[1],t3[1]);}if(dp[t][f]!=inf)return dp[t][f];if(f>=f1[t])dp[t][f]=min(dp[t][f],dfs(t-1,f-f1[t])+t1[t]);dp[t][f]=min(dp[t][f],dfs(t-1,f)+t2[t]);dp[t][f]=min(dp[t][f],dfs(t-1,min(f+f2[t],m))+t3[t]);return dp[t][f]; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",t1+i,t2+i,t3+i,f1+i,f2+i);memset(dp,inf,sizeof(dp));dp[0][m]=0;cout<<dfs(n,m)<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的ZOJ - 2972 Hurdles of 110m(记忆化搜索/动态规划)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。