本文共 2431 字，大约阅读时间需要 8 分钟。

题目链接:

时间：1 秒 空间：512 MB

问题描述

某花店现有f束花，每一束花的品种都不一样，同时至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，从左到右按1到V顺序编号，V是花瓶的数目。花束可以移动，并且每束花用1到f的整数标识。如果i<j，则花束i必须放在花束j左边的花瓶中。

例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有花束在放入花瓶时必须保持其标识数的顺序，即杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶只能放一束花。

每个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为0。在上述的例子中，花瓶与花束的不同搭配所具有的美学值，可以用下面的表格10-1来表示：

根据表格，杜鹃花放在花瓶2中，会显得更好看，但若放在花瓶4中，则显得很难看。

输入格式

第1行两个整数f和V，分别为花束数和花瓶数(1≤f≤100,f≤V≤100)。接下来是矩阵Aij，它有i行，每行j个整数，Aij表示花束i摆放在花瓶j中的美学值。

输出格式

第1行是一个整数，为最大的美学值；接下来有f行，每行两个数，为那束花放入那个花瓶的编号。

样例输入

3  5

7 23 -5 -24 16

5 21 -4 10 23

-21 5 -4 -20 20

样例输出

53

2 4 5

解题思路

dp[i][j]表示前i朵花放入前j个瓶子的最大值，则第一种状态转移方程为:

dp[i][j] = max(dp[i][j], max(dp[i-1][i-1~j-1])+a[i][j]), 其中max(dp[i-1][i-1~j-1])表示上一层的最大值。 第二种为:dp[i][j] = max(dp[i][j-1], dp[i-1][j-1]+a[i][j]), 注意初始化。

Accepted Code 1:

#include 
   
    using namespace std;const int inf = 0x3f3f3f3f;int dp[105][105], a[105][105];void print(int n, int m) {    if (n <= 0)        return ;    int i = n;    while (dp[n][i] != m)        i++;    print(n - 1, m - a[n][i]);    printf("%d ", i);}int main() {    int n, m;    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= m; j++) {            scanf("%d", &a[i][j]);            dp[i][j] = -inf;        }    }    dp[0][0] = 0;    for (int i = 1; i <= n; i++) {        int max_ = -inf;        for (int j = i; j <= m; j++) {            max_ = max(dp[i - 1][j - 1], max_);            dp[i][j] = max(dp[i][j], max_ + a[i][j]);        }    }    int max_ = -inf;    for (int i = 1; i <= m; i++)        max_ = max(max_, dp[n][i]);    printf("%d\n", max_);    print(n, max_);    return 0;}
   

Accepted Code 2:

#include 
   
    using namespace std;const int inf = 0x3f3f3f3f;int dp[105][105], a[105][105];void print(int n, int m) {    if (n <= 0)        return ;    int i = n;    while (dp[n][i] != m)        i++;    print(n - 1, m - a[n][i]);    printf("%d ", i);}int main() {    int n, m;    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= m; j++) {            scanf("%d", &a[i][j]);            dp[i][j] = -inf;        }    }    for (int i = 0; i <= n; i++)//注意初始化         dp[i][0] = -inf;    dp[0][0] = 0;    for (int i = 1; i <= n; i++)        for (int j = i; j <= m; j++)            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + a[i][j]);    printf("%d\n", dp[n][m]);    print(n, dp[n][m]);    return 0;}
   

转载地址：http://uqftf.baihongyu.com/