P2066 机器分配

· · 题解

一道经典的区间DP练习题。

设f[i][j]为前i个公司总共分配j台机器的最大利润。对于第i家子公司，我们可以给其分配的机器台数为：

0,1,2……m

所以在该区间内枚举一个值k，状态转移方程即为：

f[i][j]=max(f[i-1][j-k],f[i][j]);

那么，如何处理方案输出问题呢？

我们设path[i][j][h]对于前i个公司共分配j台机器的最优方案，第h个公司应分配多少台机器，当状态发生转移时，更新path数组即可。最终的答案就存放在path[n][m][i]之中。

贴代码：

#include<bits/stdc++.h>
using namespace std;
int f[11][16],graph[11][16],path[11][16][11],n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cin>>graph[i][j];
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)    
            for(int k=0;k<=j;k++)
            {
                if (f[i][j]<f[i-1][j-k]+graph[i][k])
                {
                    f[i][j]=f[i-1][j-k]+graph[i][k];
                    for(int h=1;h<i;h++) path[i][j][h]=path[i-1][j-k][h];//path数组只有在状态发生转移时才更新
                    path[i][j][i]=k;
                }    
            }
    cout<<f[n][m]<<endl;
    for(int i=1;i<=n;i++) cout<<i<<" "<<path[n][m][i]<<endl;
    return 0;
}

如果你依照上述思想写出了dp程序并提交，恭喜你，只有90分。

那么这是为什么呢？

回到题面，我们会发现小小的一行字，人畜无害的样子：

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

你会发现如果这样做，方案输出是错的。

如何使字典序最小呢？这需要我们倒着枚举。

设表示的意思为“不给”第i家公司k台机器（k的值域同上），那么状态转移方程需改为：

f[i][j]=max(f[i][k],f[i-1][k]+graph[i][j-k]);

再根据这个，对于path数组的更新操作进行一些微调，即可得到满分程序了：

#include<bits/stdc++.h>
using namespace std;
int f[11][16],graph[11][16],path[11][16][11],n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cin>>graph[i][j];
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)    
            for(int k=0;k<=j;k++)
            {
                if (f[i][j]<f[i-1][k]+graph[i][j-k])
                {
                    f[i][j]=f[i-1][k]+graph[i][j-k];
                    for(int h=1;h<i;h++) path[i][j][h]=path[i-1][k][h];
                    path[i][j][i]=j-k;//因为改为了“不给”第i家公司k台机器，所以必须如此调整
                }
            }
    cout<<f[n][m]<<endl;
    for(int i=1;i<=n;i++) cout<<i<<" "<<path[n][m][i]<<endl;
    return 0;
}