题目描述

总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤100，N≤100。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

输入

第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；

接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。

输出

第一行输出最大盈利值；

接下N行，每行有2个数，即分公司编号和该分公司获得设备台数。

样例

输入样例

3 3           //3个分公司分3台机器
30 40 50
20 30 50
20 25 30

输出样例

70                      //最大盈利值为70
1 1                     //第一分公司分1台
2 1                     //第二分公司分1台
3 1                     //第三分公司分1台

源代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define M 5000
int f[M][M];
int n, m, ans;
int c[M][M];

void print(int i, int j) {
    if (!i) return;
    for (int k = 0; k <= j; k++) {
        if (ans == f[i - 1][k] + c[i][j - k]) {
            ans = f[i - 1][k];
            print(i - 1, k);
            printf("%d %d\n", i, j - k);
            break;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) scanf("%d", &c[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int maxx = 0;
            for (int k = 0; k <= j; k++) {
                maxx = max(f[i - 1][k] + c[i][j - k], maxx);
            }
            f[i][j] = maxx;
        }
    printf("%d\n", f[n][m]);
    ans = f[n][m];
    print(n, m);
    return 0;
}