? ??有一排N個(gè)數(shù)，你和小明2個(gè)人玩游戲，每個(gè)人輪流從2端取數(shù)，每次可以從左或右取，不能從中間取。你取的所有的數(shù)的和是你的得分，小明取的所有的數(shù)的和是小明的得分。如果你先取，你最多比小明多得多少分？
輸入格式
??第一行：一個(gè)整數(shù)n，范圍在[0, 100]。
??第二行：n個(gè)整數(shù)，每個(gè)數(shù)范圍在[1, 10000]。
輸出格式
??小明足夠聰明時(shí)，你最多多得的分?jǐn)?shù)。
輸入/輸出例子1
輸入：
? 4
? 3 2 9 1
輸出：
??9
樣例解釋：??????????
第1輪你取3；
第2輪他取2；
第3輪你取9；
第4輪他取1；
(3+9)-(2+1) = 9
樣例解釋
無
代碼：
#include<bits/stdc++.h>
using namespace std;
int n,f[105][105],a[105],ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],f[i][i]=a[i];
for(int i=1;i<=n;i++)
for(int j=1;j+i<=n;j++)
f[j][j+i]=max(-f[j+1][j+i]+a[j],-f[j][i+j-1]+a[i+j]);
cout<<f[1][n];
return 0;
}
有n個(gè)數(shù)字（0到99）排成一行，每一次可以將相鄰的兩個(gè)數(shù)字相加并對100取模（即除以100的余數(shù)），將結(jié)果取代之前的兩個(gè)數(shù)，一次操作的花費(fèi)為兩個(gè)數(shù)字相乘。經(jīng)過n-1次操作后剩下一個(gè)數(shù)，問剩下一個(gè)數(shù)時(shí)總花費(fèi)的最小值。
輸入格式
有若干組數(shù)據(jù)，每組數(shù)據(jù)第一行為一個(gè)正整數(shù)n（n<=100）表示數(shù)字的個(gè)數(shù)。
第二行為n個(gè)正整數(shù)（0到99）
輸出格式
每組數(shù)據(jù)對應(yīng)的最小花費(fèi)。
輸入/輸出例子1
輸入：
2
18 19
3
40 60 20
?
輸出：
342
2400
樣例解釋
對于第二組數(shù)據(jù)有兩種方案：
1、??先將（40和60）相加得0，再將0?和20相加得20，總花費(fèi)為40*60+0*20=2400
2、??先將（60和20）相加得80，再將40和80相加得20，總花費(fèi)為60*20+40*80=4400
顯然第一種方案較好。
?
樣例解釋
無
代碼：
#include<bits/stdc++.h>
using namespace std;
int n,a[105],f[105][105],d[105];
int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0;i <= 105;i++){
for(int j = 1;j <= 105;j++)
f[i][j] = 1250000;
}
for(int i = 1;i <= 105;i++){
d[i] = 0;
}
for(int i = 1;i <= n;i++){
cin>>a[i];
d[i] = d[i-1]+a[i];
f[i][i] = 0;
}
for(int i = 2;i <= n;i++)
for(int j = i;j <= n;j++){
int lt = j-i+1;
for(int k = lt;k < j;k++){
int x = (d[k]-d[lt-1])%100;
int y = (d[j]-d[k])%100;
f[lt][j]=min(f[lt][j],f[lt][k]+f[k+1][j]+x*y);
}
}
cout<<f[1][n]<<endl;
}
return 0;
}- 測試
為了挽救災(zāi)區(qū)同胞的生命，心系災(zāi)區(qū)同胞的你準(zhǔn)備自己采購一些糧食支援災(zāi)區(qū)，現(xiàn)在假設(shè)你一共有資金n元，而市場有m種大米，每種大米都是袋裝產(chǎn)品，其價(jià)格不等，并且只能整袋購買。請問：你用有限的資金最多能采購多少公斤糧食呢？
輸入格式
輸入數(shù)據(jù)首先包含一個(gè)正整數(shù)C，表示有C（C<=10）組測試數(shù)據(jù)，每組測試數(shù)據(jù)的第一行是兩個(gè)整數(shù)n和m(1<=n<=100, 1<=m<=100),分別表示經(jīng)費(fèi)的金額和大米的種類，然后是m行數(shù)據(jù)，每行包含3個(gè)數(shù)p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分別表示每袋的價(jià)格、每袋的重量以及對應(yīng)種類大米的袋數(shù)。
輸出格式
對于每組測試數(shù)據(jù)，請輸出能夠購買大米的最多重量，你可以假設(shè)經(jīng)費(fèi)買不光所有的大米，并且經(jīng)費(fèi)你可以不用完。每個(gè)數(shù)據(jù)的輸出占一行。
輸入/輸出例子1
輸入：
1
8 2
2 100 4
4 100 2
輸出：
400
樣例解釋
無
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105],b[105],c[105];
int dp[105];
int n,m;
int main()
{
int C;
scanf("%d",&C);
while(C--)
{
memset(dp, 0, sizeof(dp));
scanf("%d %d",&n,&m);
for(int i=0; i<m; i++)
{
scanf("%d %d %d",&a[i],&b[i],&c[i]);
}
for(int i=0; i<m; i++)
{
for(int j=1; j<=c[i]; j++)
{
for(int k=n; k>=a[i]*j; k--)
{
dp[k]=max(dp[k-a[i]]+b[i], dp[k]);
}
}
}
printf("%d\n",dp[n]);
}
return 0;
}有N張光盤，每張光盤有一個(gè)價(jià)錢，現(xiàn)在要從N張光盤中買M張，預(yù)算為L，每張光盤有一個(gè)快樂值，要求在不超過預(yù)算并且恰好買M張，使得快樂值總和最大。
輸入格式
第一行為一個(gè)正整數(shù)T（1<=T<=5）表示測試數(shù)據(jù)個(gè)數(shù)
每組測試數(shù)據(jù)第一行為三個(gè)正整數(shù)N（N<=100）,M（M<=N）,L(L<=1000)
接下來的N行每行有兩個(gè)正整數(shù)，分別是光盤的價(jià)錢與快樂值。
輸出格式
每組數(shù)據(jù)對應(yīng)的最大快樂值總和（保證小于2^31）。若無解則輸出0.
輸入/輸出例子1
輸入：
1
3 2 10
11 100
1 2
9 1
輸出：
3
樣例解釋
無
代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 1010;
const int INF = 1 << 31;
struct Movie
{
int t,v;
};
Movie movie[MAXN];
int dp[MAXN][MAXN];
int n,m,l;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&l);
for(int i = 1;i <= m;i++)
for(int j = 0;j <= l;j++)
dp[j][i] = -INF;
for(int j = 0;j <= l;j++)
dp[j][0] = 0;
for(int i = 1;i <= n;i++)
scanf("%d%d",&movie[i].t,&movie[i].v);
for(int i = 1;i <= n;i++)
for(int j = l;j >= movie[i].t;j--)
for(int k = m;k >= 1;k--)
dp[j][k] = max(dp[j][k],dp[j-movie[i].t][k-1]+movie[i].v);
int ans = 0;
for(int i = 1;i <= l;i++)
if(dp[i][m] > ans)
ans = dp[i][m];
printf("%d\n",ans);
}
return 0;
}總結(jié)：
狀態(tài)：線性DP --?--?區(qū)間DP
階段：長度文章來源：http://www.zghlxwxcb.cn/news/detail-653658.html
階段的方向：2種??------?取決于“子問題”文章來源地址http://www.zghlxwxcb.cn/news/detail-653658.html
到了這里，關(guān)于c++11/c++98動(dòng)態(tài)規(guī)劃入門第5課，經(jīng)典DP問題 --- 區(qū)間的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![動(dòng)態(tài)規(guī)劃——區(qū)間dp [石子合并]](https://imgs.yssmx.com/Uploads/2024/02/533080-1.png)
