洛谷-P2066 机器分配(区间DP)

题目背景

无

题目描述

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

输入格式

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

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

输出格式

第1行为最大盈利值

第2到第n为第i分公司分x台

P.S.要求答案的字典序最小

输入输出样例

输入 #1

3 3
30 40 50
20 30 50
20 25 30

输出 #1

70
1 1
2 1
3 1

---

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<int> > d(20, vector<int>(20)), 
    value(20, vector<int>(20)), pre(20, vector<int>(20));

void PathPrint(int i, int j, int sum)
{
    if (!i) return; //递归终止条件
    for (int k = 0; k <= j; ++k) {
        if (sum == d[i - 1][k] + value[i][j - k]) {
            PathPrint(i - 1, k, d[i - 1][k]);
            cout << i << ' ' << (j - k) << endl;
            break;
        }
    }
}

void solve()
{
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = 0; k <= j; ++k) {
                d[i][j] = max(d[i][j], d[i - 1][k] + value[i][j - k]);
            }
        }
    }
    cout << d[n][m] << endl;
    PathPrint(n, m, d[n][m]);
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> value[i][j];
        }
    }

    solve();

    return 0;
}

用d[i][j]代表第i个公司分得j台机器所能获得最大价值，状态转移方程（state transition equation）是： $$ d[i][j] = \max(d[i - 1][k] + value[i][j - k]), 0 \leq k \leq j $$ 思路就是前i-1个公司分配k台机器，最后一个公司分配j-k台，取所有价值中的最大值。注意题目条件里数据范围在20，所以$O(n^3)$是可行的。另外路径输出的技巧也很值得学习。