【题解】机器分配

状态定义：dp[i][j]：对前i家公司分配j台设备能获得的最大盈利。
状态转移方程
记p[i][j]为给第i家公司分配j台设备能获得的盈利。
集合：前i家公司分配j台设备的方案
分割集合：第i家公司分配几台设备

如果不给第i家公司分配设备，那么需要给前i-1家公司分配j台设备，最大盈利为dp[i][j] = dp[i-1][j]
如果给第i家公司分配1台设备，那么需要给前i-1家公司分配j-1台设备，最大盈利为dp[i][j] = dp[i-1][j-1]+p[i][1]
如果给第i家公司分配2台设备，那么需要给前i-1家公司分配j-2台设备，最大盈利为dp[i][j] = dp[i-1][j-2]+p[i][2]
…
如果给第i家公司分配j台设备，那么需要给前i-1家公司分配0台设备，最大盈利为dp[i][j] = dp[i-1][0]+p[i][j]
概括上述情况，k从0到j循环，给第i家公司分配k台设备，需要给前i-1家公司分配j-k太设备，最大盈利为dp[i][j] = dp[i-1][j-k]+p[i][k]
以上所有情况取最大值。

#include<bits/stdc++.h>
using namespace std;
#define N 20
int n, m, p[N][N], g[N][N], dp[N][N];//dp[i][j]:对前i家公司分配j台设备能获得的最大盈利。
void show(int x, int k)//输出前x家公司分配k台设备的情况 
{
    if(x == 0)
        return;
    show(x-1, k-g[x][k]);
    cout << x << ' ' << g[x][k] << endl;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> p[i][j];//p[i][j]:第i公司获得j台设备能获得的盈利 
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            for(int k = 0; k <= j; ++k)//第i家公司分配k台设备 
            {
                if(dp[i][j] <= dp[i-1][j-k]+p[i][k])//本题隐藏条件有：前面的公司尽量少分配，后面的公司尽量多分配。所以要选择尽量大的k赋值给g[i][k] 
                {
                    dp[i][j] = dp[i-1][j-k]+p[i][k];
                    g[i][j] = k;//g[i][j]:给前i家公司分配j台设备时，第i家公司分到的设备数量
                }
            }
    cout << dp[n][m] << endl;
    show(n, m); 
    return 0;
}