用php做的网站用什么数据库,沈阳网站备案照相,商城展示网站建设,小程序商店多少钱观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径#xff0c;使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。 在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。 【输入】 第一个行包含R(1≤ R≤1000)…观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。 在上面的样例中,从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 【输出样例】 86dp从下往上找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]; #includeiostream
using namespace std;
int a[1003][1002];
int main(){int n;cinn;for(int i1;in;i){for(int j1;ji;j)cina[i][j];}for(int in-1;i1;i--){for(int j1;ji;j)a[i][j]max(a[i1][j],a[i1][j1]);}couta[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)若存在i1i2i3…iei1i2i3…ie 且有b(i1)b(i2)…b(ie)b(i1)b(i2)…b(ie)则称为长度为e的不下降序列。程序要求当原数列出之后求出最长的不下降序列。 例如13791638243718441921226315。例中13161819212263就是一个长度为7的不下降序列同时也有7 9161819212263组成的长度为8的不下降序列。 【输入】 第一行为n,第二行为用空格隔开的n个整数。 【输出】 第一行为输出最大个数max(形式见样例) 第二行为max个整数形成的不下降序列,答案可能不唯一输出一种就可以了本题进行特殊评测。 【输入样例】 14
13 7 9 16 38 24 37 18 44 19 21 22 63 15 【输出样例】 max8
7 9 16 18 19 21 22 63dp: F[n]为以a[n]为结尾的最长递增序列长度 F[n]max{F[i]1a[i]a[n]} 答案是F[i]的最大值1in) #includeiostream
using namespace std;
int a[205];
int F[205];
int main(){int n,maxx,maxxx0;;cinn;for(int i1;in;i){cina[i];maxx0;for(int j1;ji;j){if(a[j]a[i]){if(F[j]maxx)maxxF[j];}}F[i]maxx1;if(F[i]maxxx)maxxxF[i];}coutmaxxxendl;return 0;
} 但是题目要求输出序列就要保存序列就多开一维F存以F[i]结尾的序列 #includeiostream
using namespace std;
int a[205];
int F[205][205];
int main(){int n,maxx,maxxx0,maxn;cinn;for(int i1;in;i){cina[i];maxx0;for(int j1;ji;j){if(a[j]a[i]){if(F[j][0]maxx){maxxF[j][0];for(int w1;wF[j][0];w)F[i][w]F[j][w];}}}F[i][0]maxx1;F[i][F[i][0]]a[i];if(F[i][0]maxxx){maxxxF[i][0];maxni;}}coutmaxmaxxxendl;for(int i1;imaxxx;i){if(i!1) cout ;coutF[maxn][i];}coutendl;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 【输出样例】 minlong19
1 3 5 8 10dp:F[i]代表从起点到i号的最短距离从前向后推F[n]min{f[i]a[i][n]a[i][n]!0}然后b[n][]记录到n的路径 #includeiostream
using namespace std;
int n;
int a[105][105];
int F[100];
int b[105][105];
int main(){cinn;for(int i1;in;i)b[i][1]1;int tn1;for(int i1;in;i){F[i]999999;for(int j1;jn;j){cina[i][j];}}for(int i1;in;i){if(a[1][i]!0){F[i]a[1][i];b[i][2]i;}}for(int i2;in;i){for(int ji1;jn;j){if(a[i][j]!0){if(a[i][j]F[i]F[j]){for(int x1;xn;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];}}}}coutminlongF[n]endl;for(int i1;in;i){if(b[n][i]0) break;if(i!1) cout ;coutb[n][i];
}
coutendl;return 0;
} 转载于:https://www.cnblogs.com/yfr2zaz/p/10610712.html
