《程序设计与算法（二）算法基础》《第六周 分治》动态规划 Triangle 最长上升子序列 公共子序列 最佳加法表达式(HARD) 1163 2757 1458 4152

1163:The Triangle

总时间限制: 
1000ms
 
内存限制: 
65536kB
描述
7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

(Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
输入
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
输出
Your program is to write to standard output. The highest sum is written as an integer.
样例输入
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
样例输出
30
/*
http://bailian.openjudge.cn/practice/1163/
1163:The Triangle
递归解法2：数字三角形的记忆递归型动归程序
*/
#include<iostream>
#include<algorithm>
#define MAX 101
using namespace std;
int D[MAX][MAX];
int sum[MAX][MAX];
int n;
int MaxSum(int i, int j)
{
    if (sum[i][j] != -1)/*说明这个路径的最大和已经算过了*/
    {
        return sum[i][j];
    }
    if (i == n)
    {
        sum[i][j] = D[i][j];
    }
    else
    {
        int x = MaxSum(i + 1, j);
        int y = MaxSum(i + 1, j + 1);
        sum[i][j] = max(x, y) + D[i][j];
    }
    return sum[i][j];
}
int main()
{
    int i, j;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j <= i; j++)
        {
            cin >> D[i][j];
            sum[i][j] = -1;
        }
    }
    cout << MaxSum(0, 0) << endl;
    return 0;

}
/*
The Triangle
递归转成递推
*/
#include<iostream>
#include<algorithm>
using namespace std;

int n;
#define MAX 101
int D[MAX][MAX];
int maxsum[MAX][MAX];

int main()
{
    int i, j;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j <= i; j++)
        {
            cin >> D[i][j];
        }
    }
    for (i = n - 1; i >= 0; i--)
    {
        for (j = 0; j <= n - 1; j++)
        {
            if (i == n - 1)
            {
                maxsum[i][j] = D[i][j];
            }
            else
            {
                maxsum[i][j] = max(maxsum[i + 1][j], maxsum[i + 1][j + 1]) + D[i][j];
            }

        }

    }
    cout << maxsum[0][0] << endl;
    return 0;
}
/*
The Triangle
递归转成递推
空间优化
用一维数组替代二维数组
进一步考虑，连maxSum 数组都可以不要，直接用 D 的第 n 行替代 maxSum 即可。
节省空间，时间复杂度不变
*/
#include<iostream>
#include<algorithm>
using namespace std;

int n;
#define MAX 101
int D[MAX][MAX];
int *maxsum;
int main()
{
    int i, j;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j <= i; j++)
        {
            cin >> D[i][j];
        }
    }
    maxsum = D[n-1];/* maxSum 指向第 n 行 */

    for (i = n - 2; i >= 0; i--)
    {
        for (j = 0; j <= n - 2; j++)
        {
            maxsum[j] = max(maxsum[j] ,maxsum[j + 1]) + D[i][j];

        }

    }
    cout << maxsum[0] << endl;
    return 0;
}

2757:最长上升子序列

总时间限制: 
2000ms
 
内存限制: 
65536kB
描述
一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
输出
最长上升子序列的长度。
样例输入
7
1 7 3 5 9 4 8
样例输出
4
/*
Dynamic Planning
http://bailian.openjudge.cn/practice/2757
2757:最长上升子序列
思路：找子问题
1. “求序列的前n 个元素的最长上升子序列的长度 是个子问题，但这样分解子问题，不具有“无后效性”
2. “求以ak（ k=1, 2, 3…N ）为终点的最长上升子序列的长度”
*/

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1010;
int a[MAXN];
int maxLen[MAXN];

int main()
{
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i];
        maxLen[i] = 1;
        for (int i = 2; i <= N; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                if (a[i] > a[j])
                {/*要遍历子问题的最长子序列，j=1,2,3..., 有可能j=2  > j=3, 所以要记录j=2时的最大值
                 ，防止j=3时，刷掉上一个实际的最优解 */
                    maxLen[i] = max(maxLen[i], maxLen[j] + 1);
                }
            }
        }
    }
    /* STL 函数*/
    cout << *max_element(maxLen + 1, maxLen + N + 1);
    return 0;
}

1458:Common Subsequence

总时间限制: 
1000ms
 
内存限制: 
65536kB
描述
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
输入
The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.
输出
For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
样例输入
abcfbc         abfcab
programming    contest 
abcd           mnp
样例输出
4
2
0

/*
http://bailian.openjudge.cn/practice/1458
1458:Common Subsequence
公共子序列
*/

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char sz1[1000];
char sz2[1000];
int maxLen[1000][1000];
int main()
{
    while (cin >> sz1 >> sz2)
    {
        int length1 = strlen(sz1);
        int length2 = strlen(sz2);
        int nTmp;
        int i, j;
        /* 边界条件,如果一个字符串没有字符，默认最长公共子序列为0 */
        for (i = 0; i <= length1; i++)
            maxLen[i][0] = 0;
        for (j = 0; j <= length2; j++)
            maxLen[0][j] = 0;
        for (i = 1; i <= length1; i++)
        {
            for (j = 1; j <= length2; j++)
            {
                if (sz1[i - 1] == sz2[j - 1])
                {
                    maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
                }
                else
                {
                    maxLen[i][j] = max(maxLen[i][j - 1], maxLen[i - 1][j]);
                }
            }
        }
        cout << maxLen[length1][length2] << endl;
    }
    return 0;
}

4152:最佳加法表达式

总时间限制: 
1000ms
 
内存限制: 
65536kB
描述

给定n个1到9的数字，要求在数字之间摆放m个加号(加号两边必须有数字），使得所得到的加法表达式的值最小，并输出该值。例如，在1234中摆放1个加号，最好的摆法就是12+34,和为36

输入
有不超过15组数据
每组数据两行。第一行是整数m，表示有m个加号要放( 0<=m<=50)
第二行是若干个数字。数字总数n不超过50,且 m <= n-1
输出
对每组数据，输出最小加法表达式的值
样例输入
2
123456
1
123456
4
12345
样例输出
102
579
15
提示
要用到高精度计算，即用数组来存放long long 都装不下的大整数，并用模拟列竖式的办法进行大整数的加法。
/*
http://bailian.openjudge.cn/practice/4152/
4152:最佳加法表达式
*/
//By Guo Wei
#include <iostream>
#include <string>
#include <cstring>
#include<algorithm>
using namespace std;
struct BigInt
{

    int num[110];
    int len;
    BigInt operator+(const BigInt & n) { //重载+，使得 a + b在 a,b都是 BigInt变量的时候能成立
        int ml = max(len, n.len);
        int carry = 0; //进位 
        BigInt result;
        for (int i = 0; i < ml; ++i) {
            result.num[i] = num[i] + n.num[i] + carry;
            if (result.num[i] >= 10) {
                carry = 1;
                result.num[i] -= 10;
            }
            else
                carry = 0;
        }
        if (carry == 1) {
            result.len = ml + 1;
            result.num[ml] = 1;
        }
        else
            result.len = ml;
        return result;
    }
    bool operator<(const BigInt & n) {
        if (len > n.len)
            return false;
        else if (len < n.len)
            return true;
        else {
            for (int i = len - 1; i >= 0; --i) {
                if (num[i] < n.num[i])
                    return true;
                else if (num[i] > n.num[i])
                    return false;
            }
            return false;
        }
    }
    BigInt() {
        len = 1;
        memset(num, 0, sizeof(num));
    }
    BigInt(const char * n, int L) { //由长度为L的char数组构造大整数。n里面的元素取值范围从 1-9。 
        memset(num, 0, sizeof(num));
        len = L;
        for (int i = 0; n[i]; ++i)
            num[len - i - 1] = n[i] - '0';
    }
};
ostream & operator <<(ostream & o, const BigInt & n)
{

    for (int i = n.len - 1; i >= 0; --i)
        o << n.num[i];
    return o;
}
const int MAXN = 60;
char a[MAXN];
BigInt Num[MAXN][MAXN];//Num[i][j]表示从第i个数字到第j个数字所构成的整数 
BigInt V[MAXN][MAXN]; //V[i][j]表示i个加号放到前j个数字中间，所能得到的最佳表达式的值。 
int main()
{
    int m, n;
    BigInt inf; //无穷大 
    inf.num[MAXN - 2] = 1;
    inf.len = MAXN - 1;

    while (cin >> m) {
        cin >> a + 1;
        n = strlen(a + 1);
        for (int i = 1; i <= n; ++i)
            for (int j = i; j <= n; ++j) {
                Num[i][j] = BigInt(a + i, j - i + 1);
            }
        for (int j = 1; j <= n; ++j) {
            V[0][j] = BigInt(a + 1, j);
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j - 1 < i)
                    V[i][j] = inf;
                else {
                    BigInt tmpMin = inf;
                    for (int k = i; k < j; ++k) {
                        BigInt tmp = V[i - 1][k] + Num[k + 1][j];
                        if (tmp < tmpMin)
                            tmpMin = tmp;
                    }
                    V[i][j] = tmpMin;
                }
            }
        }
        cout << V[m][n] << endl;
    }
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/focus-z/p/11610310.html