题目链接:http://www.jxsfczx.cn:888/problem/320
时间：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 <bits/stdc++.h>
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 <bits/stdc++.h>
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;
}