题解 P2066 【机器分配】
ouuan
2018-03-10 11:53:20
照例看了一眼第一页的所有题解，发现没有dp数组1维path数组2维的，唯一一个不用path数组的是递归输出而且输出复杂度大概看了一眼貌似是O(nm)，所以讲一下我小小的优化。
f(i,j)表示将j台机器分给1~i公司的最大盈利，w[i][j]表示第i公司有j台机器的盈利
转移方程就是f(i,j)=max(k∈[0,j]){f(i+1,j-k)+w[i][j]}
重点在如何优化数组大小（虽然这题数据极小）
注意到转移方程里只用到了f(i+1,l)(l∈[0,j])，因此只要从大到小枚举j就可以在dp数组里去掉i这一维
接下来是输出，我是用ans数组保存f(i,j)取最大时k的值，然后依次求出f(i,j)是由f(i+1,?)转移而来就可以输出方案了。字典序最小所以k要正序枚举，比较f[j]与f[j-k]+w[i][k]大小时不能取等；为方便正序输出所以i倒序枚举（如果正序枚举i答案就是f(n,m)，输出就要从n开始，如果要正序输出就得用数组保存）。
具体细节看程序吧：
```
#include <iostream>
using namespace std;
int f[20],n,m,w[20][20],ans[20][20];
int main()
{
int i,j,k;
cin>>n>>m;
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
cin>>w[i][j];
}
}
for (i=n;i>0;--i)
{
for (j=m;j>=0;--j)
{
for (k=1;k<=j;++k)
{
if (f[j-k]+w[i][k]>f[j])
{
f[j]=f[j-k]+w[i][k];
ans[i][j]=k; //保存f(i,j)取最大时k的值
}
}
}
}
cout<<f[m];
for (i=1,j=m;i<=n;++i)
{
cout<<endl<<i<<" "<<ans[i][j];
j-=ans[i][j]; //算出最优方案第i+1~n公司共使用了几台机器，也就是f(i,j)是由f(i+1,?)转移过来的
}
return 0;
}
```
其实正序枚举i倒序枚举k也是可以的，只不过有些麻烦：
```
#include <iostream>
using namespace std;
int f[20],n,m,w[20][20],ans[20][20],out[20];
int main()
{
int i,j,k;
bool flag;
cin>>n>>m;
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
cin>>w[i][j];
}
}
for (i=1;i<=n;++i)
{
for (j=m;j>=0;--j)
{
flag=true; //flag用来标识当前f(i,j)的最大值是否为k=0时取的，因为倒序枚举的话不能算k=0的情况，否则f[j-k]+w[i][k]==f[j]必定满足，ans里面就全是0了；但如果是k≠0时f(i,j)同样可以取到最大值，就没有取到字典序最小
for (k=j;k>0;--k)
{
if (flag&&f[j-k]+w[i][k]>=f[j]||f[j-k]+w[i][k]>f[j])
{
flag=false;
f[j]=f[j-k]+w[i][k];
ans[i][j]=k;
}
}
}
}
cout<<f[m];
for (i=n,j=m;i>0;--i)
{
out[i]=ans[i][j]; //将结果保存在out数组里
j-=ans[i][j];
}
for (i=1;i<=n;++i)
{
cout<<endl<<i<<" "<<out[i]; //正序输出
}
return 0;
}
```