基本動態規劃題集

觀察下面的數字金字塔。寫一個程序查找從最高點到底部任意處結束的路徑，使路徑經過數字的和最大。每一步可以從當前點走到左下方的點也可以到達右下方的點。

在上面的樣例中,從13到8到26到15到24的路徑產生了最大的和86。

【輸入】

第一個行包含R(1≤ R≤1000)，表示行的數目。

后面每行為這個數字金字塔特定行包含的整數。

所有的被供應的整數是非負的且不大于100。

?

【輸出】

單獨的一行，包含那個可能得到的最大的和。

【輸入樣例】

5
13
11 8
12 7  26
6  14 15 8
12 7  13 24 11

【輸出樣例】

86
dp：
從下往上找F[1][1]=min{F[2][1]+A[1][1],F[2][2]+A[1][1]}
從F[N-1][1]到F[n-1][n-1]
一行行找到F[1][1];

#include<iostream>
using namespace std;
int a[1003][1002];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++)cin>>a[i][j];}for(int i=n-1;i>=1;i--){for(int j=1;j<=i;j++)a[i][j]+=max(a[i+1][j],a[i+1][j+1]);}cout<<a[1][1]<<endl;return 0;
} 

1259：【例9.3】求最長不下降序列

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 6847 ??? 通過數: 2146?

【題目描述】

設有由n(1≤n≤200)n(1≤n≤200)個不相同的整數組成的數列，記為:b(1)、b(2)、……、b(n)b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)b(i)≠b(j)(i≠j)，若存在i1<i2<i3<…<iei1<i2<i3<…<ie?且有b(i1)<b(i2)<…<b(ie)b(i1)<b(i2)<…<b(ie)則稱為長度為e的不下降序列。程序要求，當原數列出之后，求出最長的不下降序列。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一個長度為7的不下降序列，同時也有7 ，9，16，18，19，21，22，63組成的長度為8的不下降序列。

?

【輸入】

第一行為n,第二行為用空格隔開的n個整數。

【輸出】

第一行為輸出最大個數max(形式見樣例)；

第二行為max個整數形成的不下降序列,答案可能不唯一，輸出一種就可以了，本題進行特殊評測。

【輸入樣例】

14
13 7 9 16 38 24 37 18 44 19 21 22 63 15

【輸出樣例】

max=8
7 9 16 18 19 21 22 63

dp:

F[n]為以a[n]為結尾的最長遞增序列長度

F[n]=max{F[i]+1&&a[i]<a[n]}

答案是F[i]的最大值（1<=i<=n)

#include<iostream>
using namespace std;
int a[205];
int F[205];
int main(){int n,maxx,maxxx=0;;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];maxx=0;for(int j=1;j<i;j++){if(a[j]<a[i]){if(F[j]>maxx)maxx=F[j];}}F[i]=maxx+1;if(F[i]>maxxx)maxxx=F[i];}cout<<maxxx<<endl;return 0;
} 

但是題目要求輸出序列，就要保存序列，就多開一維F，存以F[i]結尾的序列

#include<iostream>
using namespace std;
int a[205];
int F[205][205];
int main(){int n,maxx,maxxx=0,maxn;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];maxx=0;for(int j=1;j<i;j++){if(a[j]<=a[i]){if(F[j][0]>maxx){maxx=F[j][0];for(int w=1;w<=F[j][0];w++)F[i][w]=F[j][w];}}}F[i][0]=maxx+1;F[i][F[i][0]]=a[i];if(F[i][0]>maxxx){maxxx=F[i][0];maxn=i;}}cout<<"max="<<maxxx<<endl;for(int i=1;i<=maxxx;i++){if(i!=1) cout<<" ";cout<<F[maxn][i];}cout<<endl;return 0;
} 

1261：【例9.5】城市交通路網

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 1680 ??? 通過數: 1240?

【題目描述】

下圖表示城市之間的交通路網，線段上的數字表示費用，單向通行由A->E。試用動態規劃的最優化原理求出A->E的最省費用。

如圖：求v1到v10的最短路徑長度及最短路徑。

【輸入】

第一行為城市的數量N;

后面是N*N的表示兩個城市間費用組成的矩陣。

【輸出】

A->E的最省費用。

【輸入樣例】

10
0  2  5  1  0  0  0  0  0  0
0  0  0  0 12 14  0  0  0  0
0  0  0  0  6 10  4  0  0  0
0  0  0  0 13 12 11  0  0  0
0  0  0  0  0  0  0  3  9  0
0  0  0  0  0  0  0  6  5  0
0  0  0  0  0  0  0  0 10  0
0  0  0  0  0  0  0  0  0  5
0  0  0  0  0  0  0  0  0  2
0  0  0  0  0  0  0  0  0  0

【輸出樣例】

minlong=19
1 3 5 8 10
dp:F[i]代表從起點到i號的最短距離
從前向后推：F[n]=min{f[i]+a[i][n]&&a[i][n]!=0}
然后b[n][]記錄到n的路徑

#include<iostream>
using namespace std;
int n;
int a[105][105];
int F[100];
int b[105][105];
int main(){cin>>n;for(int i=1;i<=n;i++)b[i][1]=1;int tn=1;for(int i=1;i<=n;i++){F[i]=999999;for(int j=1;j<=n;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){if(a[1][i]!=0){F[i]=a[1][i];b[i][2]=i;}}for(int i=2;i<n;i++){for(int j=i+1;j<=n;j++){if(a[i][j]!=0){if(a[i][j]+F[i]<F[j]){for(int x=1;x<=n;x++){if(b[i][x]!=0)b[j][x]=b[i][x];else{b[j][x]=j;break;}}F[j]=a[i][j]+F[i];}}}}cout<<"minlong="<<F[n]<<endl;for(int i=1;i<=n;i++){if(b[n][i]==0) break;if(i!=1) cout<<" ";cout<<b[n][i];
}
cout<<endl;return 0;
} 

?