柚子快報邀請碼778899分享：算法 [藍橋杯學習]動態(tài)規(guī)劃
柚子快報邀請碼778899分享：算法 [藍橋杯學習]動態(tài)規(guī)劃
題目描述 蒜頭君很喜歡爬樓梯，但是蒜頭君腿不夠長，每次蒜頭君最多只能一步跨越兩個階梯。比如他初始在樓底，跨越一個階梯到達 1 號階梯，或者跨越兩個階梯到達 2 號階梯。如下圖
為了選出一種最輕松的爬樓梯的方式，蒜頭君想把所有不同的到達樓頂?shù)姆绞蕉紘L試一遍。對于一共有 n 個階梯的樓梯，蒜頭君一共有多少總方法從樓底到達樓頂。
由于最后答案可能很大，輸出最后的答案對 100007 取模的結(jié)果。?
#include
#include
using namespace std;
int main()
{
int n,dp[1000];
cin>>n;
dp[0]=dp[1]=1;
for(int i=2;i<=n;i++)
{
dp[i]=(dp[i-1]+dp[i-2])%100007;
}
cout>>dp[n]>>endl;
return 0;
}
爬樓梯2 蒜頭軍可以跳躍任意奇數(shù)的階梯
#include
#include
using namespace std;
int main()
{
int n,dp[1000];
cin>>n;
dp[0]=1;
for(int i=2;i<=n;i++)
{
for(int j=i-1;j>0;j-=2)
{
dp[i]=dp[i]+dp[j];
dp[i]%=10007;
}
}
cout>>dp[n]>>endl;
return 0;
}
問題 有一個小球掉落在一串連續(xù)的彈簧板上，小球落到某一個彈簧板后，會被彈到某一個地點，直到小球被彈到彈簧板以外的地方。
假設有 n 個連續(xù)的彈簧板，每個彈簧板占一個單位距離，a[i] 代表代表第 i 個彈簧板會把小球向前彈 a[i] 個距離。比如位置 1的彈簧能讓小球前進 2 個距離到達位置 3。如果小球落到某個彈簧板后，經(jīng)過一系列彈跳會被彈出彈簧板，那么小球就能從這個彈簧板彈出來?，F(xiàn)在希望你計算出小球從任意一個彈簧板落下，最多會被彈多少次后，才會彈出彈簧板。
輸入格式
第一個行輸入一個 n 代表一共有 n 個彈簧板。第二行輸入 n 個數(shù)字，中間用空格分開。第 i 個數(shù)字 a[i] 代表第 i 個彈簧板可以讓小球移動的距離。
數(shù)據(jù)約定：
對于 50% 的數(shù)據(jù)：1 ≤ n ≤ 1000, 0 < a[i]≤30。
對于 100% 的數(shù)據(jù)：1≤n≤100000 , 0 < a[i]≤30。
輸出格式
輸出一個整數(shù)，代表小球最多經(jīng)過多少次才能彈出彈簧板。?
#include
#include
#include
#include
using namespace std;
int main()
{
int n,a[1000],dp[1000],ans=0;
cin>>n;
for(int i=0;i { cin>>a[i]; } memset(dp,0,sizeof(dp)); for(int j=n;j>0;j--) { /*dp[j+a[j]]=dp[j]+1; ans=max(ans,dp[j+a[j]]);*/ dp[j]=dp[j+a[j]]+1; ans=max(dp[j],ans) } cout< return 0; } 題目描述： 工作空閑之余，蒜頭君經(jīng)常帶著同事們做游戲，最近蒜頭君發(fā)明了一個好玩的新游戲：n 位同事圍成一個圈，同事 A 手里拿著一個兔妮妮的娃娃。蒜頭君喊游戲開始，每位手里拿著娃娃的同事可以選擇將娃娃傳給左邊或者右邊的同學，當蒜頭君喊游戲結(jié)束時，停止傳娃娃。此時手里拿著娃娃的同事即是敗者。 玩了幾輪之后，蒜頭君想到一個問題：有多少種不同的方法，使得從同事 A 開始傳娃娃，傳了 m 次之后又回到了同事 A 手里。兩種方法，如果接娃娃的同事不同，或者接娃娃的順序不同均視為不同的方法。例如1?>2?>3?>1 和 1->3->2->1 是兩種不同的方法。 輸入格式 輸入一行，輸入兩個整數(shù)n,m(3≤n≤30,1≤m≤30)，表示一共有 n 位同事一起游戲，一共傳 m 次娃娃。 輸出格式 輸出一行，輸出一個整數(shù)，表示一共有多少種不同的傳娃娃方法。 樣例輸入 3 3 樣例輸出 ２? #include #include #include #include using namespace std; int main() { int n,m,i,j; cin>>n>>m; int f[m+1][n+1];//考慮當前傳到誰手里，傳了多少次 memset(f,0,sizeof(f)); f[0][1]=1;//第一個人傳走時傳了0次，就一種方法 for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if(j==1) { f[i][j]=f[i-1][n]+f[i-1][2]; } else if(j==n) { f[i][j]=f[i-1][1]+f[i-1][n-1]; } else { f[i][j]=f[i-1][j-1]+f[i-1][j+1]; } } } cout< return 0; } 蒜頭君在玩一款逃生的游戲。在一個n×m 的矩形地圖上，蒜頭位于其中一個點。地圖上每個格子有加血的藥劑，和掉血的火焰，藥劑的藥效不同，火焰的大小也不同，每個格子上有一個數(shù)字，如果格子上的數(shù)字是正數(shù)說明是一個藥劑代表增加的生命值，如果是負數(shù)說明是火焰代表失去的生命值。 蒜頭初始化有 v 點血量，他的血量上限是 c，任何時刻他的生命值都不能大于血量上限，如果血量為 0 則會死亡，不能繼續(xù)游戲。 矩形地圖上的四個角(1,1)，(1,m)，(n,1)，(n,m)為游戲的出口。游戲中只要選定了一個出口，就必須朝著這個方向走。例如，選擇了左下的出口，就只能往左和下兩個方向前進，選擇了右上的出口，就只能往右和上兩個方向前進，左上和右下方向的出口同理。 如果成功逃生，那么剩余生命值越高，則游戲分數(shù)越高。為了能拿到最高分，請你幫忙計算如果成功逃生最多能剩余多少血量，如果不能逃生輸出 -1。 輸入格式 第一行依次輸入整數(shù) n，m，x，y，v，c（1 接下來 n 行，每行有 m 個數(shù)字，代表地圖信息。（每個數(shù)字的絕對值不大于100，地圖中蒜頭君的初始位置的值一定為 0） 輸入格式 第一行依次輸入整數(shù) n，m，x，y，v，c（1 接下來 n 行，每行有 m 個數(shù)字，代表地圖信息。（每個數(shù)字的絕對值不大于100，地圖中蒜頭君的初始位置的值一定為 0） 輸出格式 一行輸出一個數(shù)字，代表成功逃生最多剩余的血量，如果失敗輸出 -1。 樣例輸入 4 4 3 2 5 10 1 2 3 4 -1 -2 -3 -4 4 0 2 1 -4 -3 -2 -1 樣例輸出 10 #include #include #include #include #include #include #include using namespace std; int n, m, x, y, v, c; int mp[1005][1005]; //地圖 int dp[1005][1005] ; //每個點的狀態(tài) int xx[4] = { -1,-1,1,1 }; //分別表示左上、右上、右下、左下方向 int yy[4] = { -1,1,1,-1 }; const int INF = 0x3f3f; int main() { //初始化 cin >> n >> m >> x >> y >> v >> c; for (int i = 1; i <= n; ++i) { for (int j = 1; j<= m; ++j) { cin >> mp[i][j]; } } //分別往四個出口走，例如往（1，1）走，前進方向只能是向左或向上，而對于此時dp[i][j]來講， //在不考慮邊界的情況他的來源只能是他的正下方dp[i+1][j]或正右方dp[i][j+1]，取max即可 for (int t = 0; t < 4; ++t) { for (int i = x; i > 0 && i <= n; i += xx[t]) for (int j = y; j > 0 && j <= m; j += yy[t]) { if (i == x && j == y) { //起點 dp[i][j] = v; } else if (i == x) { //如果跟起點同一行，則只能為列變化 dp[i][j] = min(c, dp[i][j - yy[t]] + mp[i][j]); //注意這里的min和下面的max代表的意義 } else if (j == y) { //如果跟起點同一列，則只能為行變化 dp[i][j] = min(c, dp[i-xx[t]][j] + mp[i][j]); } else { dp[i][j] = min(c, max(dp[i - xx[t]][j], dp[i][j - yy[t]])+mp[i][j]); } if (dp[i][j] <= 0) { //已經(jīng)死掉 dp[i][j] = -INF; } } } int ans = max(max(dp[1][1], dp[1][m]), max(dp[n][1], dp[n][m])); if (ans <= 0) { cout << -1 << endl; return 0; } else { cout << ans << endl; } return 0; } 在一個夜黑風高的晚上，有n（n <= 50）個小朋友在橋的這邊，現(xiàn)在他們需要過橋，但是由于橋很窄，每次只允許不大于兩人通過，他們只有一個手電筒，所以每次過橋的兩個人需要把手電筒帶回來，i號小朋友過橋的時間為a[i]，兩個人過橋的總時間為二者中時間長者。問所有小朋友過橋的總時間最短是多少。? 分析 1、將a[n]從小到大進行排序； 2、考慮第i個人在橋的這邊， 假設前i-1個人都在橋?qū)γ嬗衐p[i]=dp[i-1]+a[1]+a[i]（讓第一個人回來送電筒，然后第i個人和第一個人過去，手電筒保持在橋?qū)γ妫?/p> 假設前i-2個人都在橋?qū)γ嬗衐p[i]=dp[i-2]+a[0]+a[i]+2*a[2]（讓第一個人回來送電筒，然后第i-1個人和第i個人過去，之后花費時間次少的第二個人過來將第一個人接過去） #include #include #include #include using namespace std; int main() { int n; cin>>n; int a[n+1],dp[n+1]; for(int i=0;i cin>>a[i]; sort(a,a+n); dp[0]=a[0]; dp[1]=a[1]; for(int i=2;i { dp[i]=min(dp[i-1]+a[0]+a[i],dp[i-2]+a[0]+a[i]+2*a[1]); } cout< return 0; } 最大子矩陣和 #include #include #include #include using namespace std; /*最大子矩陣和*/ int main() { long long perfix_sum[101][101],a[101][101]; int n,m,i,j,k; long long ans=0,sum; cin>>n>>m; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>a[i][j]; ans=max(a[i][j],ans); } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { perfix_sum[i][j]+=perfix_sum[i-1][j]+a[i][j]; } } for(i=1;i<=n;i++) { for(j=i;j<=n;j++) { sum=0; for(k=1;k { if(sum+perfix_sum[j][k]-perfix_sum[i-1][k]<0) sum=0; else sum+=perfix_sum[j][k]-perfix_sum[i-1][k]; ans=max(sum,ans); } } } cout< return 0; } 問題描述 給定有 n 個數(shù)的 A 序列：A1,A2,A3…An 。對于這個序列，我們想得到一個子序列 Ap1,Ap2?Api?Apm(1≤p1< p2 #include #include #include #include using namespace std; int main() { int n,i,j,a[1000]; cin>>n; int** dp=new int*[n]; for(i=0;i dp[i]=new int[n]; for(i=0;i cin>>a[i]; for(i=0;i { for(j=0;j dp[i][j]=0; } for(i=0;i { dp[0][i]=1; for(j=0;j { if(a[j]>=a[i]) { dp[0][i]=max(dp[0][i],dp[0][j]+1); } } } for(i=n-1;i>=0;i--) { dp[1][i]=1; for(j=n-1;j>i;j--) { if(a[j]>=a[i]) { dp[1][i]=max(dp[1][i],dp[1][j]+1); } } } int ans=0; for(i=0;i ans=max(ans,dp[0][i]+dp[1][i]-1); cout< } 柚子快報邀請碼778899分享：算法 [藍橋杯學習]動態(tài)規(guī)劃 推薦閱讀
本文內(nèi)容根據(jù)網(wǎng)絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Souq外貿(mào)尋寶坊
