柚子快報(bào)邀請碼778899分享：算法 [藍(lán)橋杯學(xué)習(xí)]動態(tài)規(guī)劃

http://yzkb.51969.com/

題目描述 蒜頭君很喜歡爬樓梯，但是蒜頭君腿不夠長，每次蒜頭君最多只能一步跨越兩個(gè)階梯。比如他初始在樓底，跨越一個(gè)階梯到達(dá) 1 號階梯，或者跨越兩個(gè)階梯到達(dá) 2 號階梯。如下圖

為了選出一種最輕松的爬樓梯的方式，蒜頭君想把所有不同的到達(dá)樓頂?shù)姆绞蕉紘L試一遍。對于一共有 n 個(gè)階梯的樓梯，蒜頭君一共有多少總方法從樓底到達(dá)樓頂。

由于最后答案可能很大，輸出最后的答案對 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;

}

問題 有一個(gè)小球掉落在一串連續(xù)的彈簧板上，小球落到某一個(gè)彈簧板后，會被彈到某一個(gè)地點(diǎn)，直到小球被彈到彈簧板以外的地方。

假設(shè)有 n 個(gè)連續(xù)的彈簧板，每個(gè)彈簧板占一個(gè)單位距離，a[i] 代表代表第 i 個(gè)彈簧板會把小球向前彈 a[i] 個(gè)距離。比如位置 1的彈簧能讓小球前進(jìn) 2 個(gè)距離到達(dá)位置 3。如果小球落到某個(gè)彈簧板后，經(jīng)過一系列彈跳會被彈出彈簧板，那么小球就能從這個(gè)彈簧板彈出來。現(xiàn)在希望你計(jì)算出小球從任意一個(gè)彈簧板落下，最多會被彈多少次后，才會彈出彈簧板。

輸入格式

第一個(gè)行輸入一個(gè) n 代表一共有 n 個(gè)彈簧板。第二行輸入 n 個(gè)數(shù)字，中間用空格分開。第 i 個(gè)數(shù)字 a[i] 代表第 i 個(gè)彈簧板可以讓小球移動的距離。

數(shù)據(jù)約定：

對于 50% 的數(shù)據(jù)：1 ≤ n ≤ 1000, 0 < a[i]≤30。

對于 100% 的數(shù)據(jù)：1≤n≤100000 , 0 < a[i]≤30。

輸出格式

輸出一個(gè)整數(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ā)明了一個(gè)好玩的新游戲：n 位同事圍成一個(gè)圈，同事 A 手里拿著一個(gè)兔妮妮的娃娃。蒜頭君喊游戲開始，每位手里拿著娃娃的同事可以選擇將娃娃傳給左邊或者右邊的同學(xué)，當(dāng)蒜頭君喊游戲結(jié)束時(shí)，停止傳娃娃。此時(shí)手里拿著娃娃的同事即是敗者。 玩了幾輪之后，蒜頭君想到一個(gè)問題：有多少種不同的方法，使得從同事 A 開始傳娃娃，傳了 m 次之后又回到了同事 A 手里。兩種方法，如果接娃娃的同事不同，或者接娃娃的順序不同均視為不同的方法。例如1?>2?>3?>1 和 1->3->2->1 是兩種不同的方法。 輸入格式 輸入一行，輸入兩個(gè)整數(shù)n,m(3≤n≤30,1≤m≤30)，表示一共有 n 位同事一起游戲，一共傳 m 次娃娃。 輸出格式 輸出一行，輸出一個(gè)整數(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];//考慮當(dāng)前傳到誰手里，傳了多少次

memset(f,0,sizeof(f));

f[0][1]=1;//第一個(gè)人傳走時(shí)傳了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;

}

蒜頭君在玩一款逃生的游戲。在一個(gè)n×m 的矩形地圖上，蒜頭位于其中一個(gè)點(diǎn)。地圖上每個(gè)格子有加血的藥劑，和掉血的火焰，藥劑的藥效不同，火焰的大小也不同，每個(gè)格子上有一個(gè)數(shù)字，如果格子上的數(shù)字是正數(shù)說明是一個(gè)藥劑代表增加的生命值，如果是負(fù)數(shù)說明是火焰代表失去的生命值。

蒜頭初始化有 v 點(diǎn)血量，他的血量上限是 c，任何時(shí)刻他的生命值都不能大于血量上限，如果血量為 0 則會死亡，不能繼續(xù)游戲。

矩形地圖上的四個(gè)角(1,1)，(1,m)，(n,1)，(n,m)為游戲的出口。游戲中只要選定了一個(gè)出口，就必須朝著這個(gè)方向走。例如，選擇了左下的出口，就只能往左和下兩個(gè)方向前進(jìn)，選擇了右上的出口，就只能往右和上兩個(gè)方向前進(jìn)，左上和右下方向的出口同理。

如果成功逃生，那么剩余生命值越高，則游戲分?jǐn)?shù)越高。為了能拿到最高分，請你幫忙計(jì)算如果成功逃生最多能剩余多少血量，如果不能逃生輸出 -1。

輸入格式 第一行依次輸入整數(shù) n，m，x，y，v，c（1

接下來 n 行，每行有 m 個(gè)數(shù)字，代表地圖信息。（每個(gè)數(shù)字的絕對值不大于100，地圖中蒜頭君的初始位置的值一定為 0）

輸入格式 第一行依次輸入整數(shù) n，m，x，y，v，c（1

接下來 n 行，每行有 m 個(gè)數(shù)字，代表地圖信息。（每個(gè)數(shù)字的絕對值不大于100，地圖中蒜頭君的初始位置的值一定為 0）

輸出格式 一行輸出一個(gè)數(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] ; //每個(gè)點(diǎn)的狀態(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];

}

}

//分別往四個(gè)出口走，例如往（1，1）走，前進(jìn)方向只能是向左或向上，而對于此時(shí)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) { //起點(diǎn)

dp[i][j] = v;

}

else if (i == x) { //如果跟起點(diǎn)同一行，則只能為列變化

dp[i][j] = min(c, dp[i][j - yy[t]] + mp[i][j]); //注意這里的min和下面的max代表的意義

}

else if (j == y) { //如果跟起點(diǎn)同一列，則只能為行變化

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;

}

在一個(gè)夜黑風(fēng)高的晚上，有n（n <= 50）個(gè)小朋友在橋的這邊，現(xiàn)在他們需要過橋，但是由于橋很窄，每次只允許不大于兩人通過，他們只有一個(gè)手電筒，所以每次過橋的兩個(gè)人需要把手電筒帶回來，i號小朋友過橋的時(shí)間為a[i]，兩個(gè)人過橋的總時(shí)間為二者中時(shí)間長者。問所有小朋友過橋的總時(shí)間最短是多少。?

分析

1、將a[n]從小到大進(jìn)行排序；

2、考慮第i個(gè)人在橋的這邊，

假設(shè)前i-1個(gè)人都在橋?qū)γ嬗衐p[i]=dp[i-1]+a[1]+a[i]（讓第一個(gè)人回來送電筒，然后第i個(gè)人和第一個(gè)人過去，手電筒保持在橋?qū)γ妫?/p>

假設(shè)前i-2個(gè)人都在橋?qū)γ嬗衐p[i]=dp[i-2]+a[0]+a[i]+2*a[2]（讓第一個(gè)人回來送電筒，然后第i-1個(gè)人和第i個(gè)人過去，之后花費(fèi)時(shí)間次少的第二個(gè)人過來將第一個(gè)人接過去）

#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 個(gè)數(shù)的 A 序列：A1,A2,A3…An 。對于這個(gè)序列，我們想得到一個(gè)子序列 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<

}

柚子快報(bào)邀請碼778899分享：算法 [藍(lán)橋杯學(xué)習(xí)]動態(tài)規(guī)劃

http://yzkb.51969.com/

推薦閱讀