信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

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

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

分析状态:

要求输出最大收益以及分配情况。

首先:必然是需要一个数组记录各公司对于i台机器的收益情况

int num[15][20];//第 i 家公司 分配 j 台机器的盈利cin >> N >> M;for(int i = 1;i <= N;i++)for(int j = 1;j <= M;j++)cin >> num[i][j];

然后是对dp数组的定义:对于需求有俩个变化量

1:公司数

2:机器数

显然机器分配给公司的最大盈利情况随着公司数和机器数是动态变化的。

例如:2台到3台时

假定3个公司2台最优解为 0 0 2

对于3公司3台的可能性有 1 1 1 和 [3  0 0] 的全排列 以及 [2 1 0] 的全排列,即我们很难通过一个dp状态和已经记录的num数组进行状态转移.=== >> 原因在于我们在进行动态转移的时候,所需要的状态量不足。

前面的动态基础模型中我们时常定义dp为第 i 个X 的 j 种情况

在这里我们如果定义dp为第i个公司j台机器的最大收益,显然是没必要的(num记录的就是这个)

因此我们可以定义dp为前i家公司分配j台机器的最优情况或者i台机器分配给j家公司的最优情况

DP状态如何转移?

首先外层对公司和机器的枚举

 for(int i = 1;i <= N;i++)//公司数for(int j = 1; j <= M;j++)//机器数

 状态转移:正如前面所说对于num数组的转移是无法通过局部最优推出全局最优的,它的转移情况特别多,因此我们通过内层增加一个for来枚举分割点,即不同机器数分配的情况(对于j台机器,给第i家公司分配k台机器的收益)

    for(int i = 1;i <= N;i++)for(int j = 1; j <= M;j++)for(int k = 0;k <= j;k++)if(dp[i][j] <= dp[i - 1][j - k] + num[i][k])dp[i][j] = dp[i - 1][j - k] + num[i][k];

显然 这样我们可以轻而易举地得到最大收益,但是对于不同公司机器的分配该如何解决?

前面提到dp[i][j]为前i家分配j台机器的最大收益值

那么每次新的一轮for i in N的枚举都是引入新的公司,而最内层是取对第i家公司在j台机器下在满足最大收益时分配的数量,那我们是否可以通过一个数组cost来记录在i家公司j台机器下,第i家公司最优解分配的机器数?

答案显而易见,可以并且实现起来也非常简单

for(int i = 1;i <= N;i++){for(int j = 1; j <= M;j++){for(int k = 0;k <= j;k++)if(dp[i][j] <= dp[i - 1][j - k] + num[i][k]){dp[i][j] = dp[i - 1][j - k] + num[i][k];cost[i][j] = k;}}}

对于输出也非常容易理解和实现:

void mycout(int x,int y)
{//x当前公司数,y当前机器数if(!x)return;mycout(x - 1,y - cost[x][y]);cout << x << " " << cost[x][y] << endl;
}

AC代码如下: 

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20;
int dp[maxn][maxn];
int num[maxn][maxn];
int cost[maxn][maxn];
int N,M;
void mycout(int x,int y)
{if(!x)return;mycout(x - 1,y - cost[x][y]);cout << x << " " << cost[x][y] << endl;
}
int main()
{cin >> N >> M;for(int i = 1;i <= N;i++)for(int j = 1; j <= M;j++)cin >> num[i][j];for(int i = 1;i <= N;i++){for(int j = 1; j <= M;j++){for(int k = 0;k <= j;k++)if(dp[i][j] <= dp[i - 1][j - k] + num[i][k]){dp[i][j] = dp[i - 1][j - k] + num[i][k];cost[i][j] = k;}}}cout << dp[N][M] << endl;mycout(N,M);return 0;
}