Luogu P2066 机器分配

题目

P2066 机器分配

分析

考虑到为每一个公司分配机器时，需要知道现在还能分配多少机器，即需要知道已分配过的公司共分得多少机器。那么这就是一个动态规划。设f[i][j]表示前i个公司共分配了j台机器。那么可以得到转移方程：

$$f[i][j]=max(f[i][j],f[i-1][j-k]+a[i][k]),k<=j$$
那么如何保存答案呢？
设ans[i][j][k]表示为前i个公司分配了j台机器时，公司k此时的机器数。随着f的更新，ans在不断改变。详见代码。

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=20;
int f[maxn][maxn],a[maxn][maxn],ans[maxn][maxn][maxn];
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)for(int k=j;k>=0;k--)//为保证字典序，应使得当前公司分配的尽量少，即把分配尽量小的k的情况保存为答案if(f[i-1][j-k]+a[i][k]>f[i][j]){f[i][j]=max(f[i][j],f[i-1][j-k]+a[i][k]);for(int l=1;l<i;l++)//前面分配过的公司此时方案改变，应当顺次更新ans[i][j][l]=ans[i-1][j-k][l];ans[i][j][i]=k;//当前公司即分配k台}printf("%d\n",f[n][m]);for(int i=1;i<=n;i++)printf("%d %d\n",i,ans[n][m][i]);return 0;
}