题解 P2066 【机器分配】

Hydra_ · 2017-09-27 18:19:49 · 题解

分析

显然是一个经典的dp题目。我们定义一个数组：f[i][j]表示前i个公司分配j台机器的最大盈利。那么求解f[i][j]的过程应该怎么求解呢？首先，我们在给第i个公司分配机器的时候，我们肯定为第i-1个公司分配过机器了，所以显然，i的状态由j的状态推导而来，那么我们需要怎么枚举呢？就是：通过枚举i个公司需要多少台机器，再枚举i-1个公司需要多少机器，再找出最大值就可以了。下面上代码：

代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int num=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())num=num*10+c-'0';
    return num;
}//快读 
int n,m,f[30][30],value[30][30],maxl;
/*以上是变量说明阶段。
f数组：f[i][j]表示前i个公司分j台机器的最大盈利
value数组：value[i][j]表示第i个公司分j台机器的盈利
*/ 
int print(int i,int j)
{
    if(i==0)return 0;
    for(int k=0;k<=j;k++)
    //k枚举了前i-1个分公司分得多少机器 
    if(maxl==f[i-1][k]+value[i][j-k])
    //知道结果倒推回去 
    {
        maxl=f[i-1][k];//步步为营的方式 
        print(i-1,k);//继续低柜求解 
        printf("%d %d\n",i,j-k);//倒序输出 
        break;//搜到了直接跳出循环 
    }
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    value[i][j]=read();
    //读入各种数据 
    for(int i=1;i<=n;i++)//枚举公司数 
    for(int j=1;j<=m;j++)//枚举机器数（总） 
    {
        maxl=0;
        for(int k=0;k<=j;k++)//枚举前i-1个公司分到的机器数 
        if(f[i-1][k]+value[i][j-k]>maxl)
        /*f[i-1][k]：前i-1个公司分k台机器的利润
        value[i][j-k]：第i个公司分j-k台机器的利润
        加起来是i个公司分j台机器的最大利润*/ 
        maxl=f[i-1][k]+value[i][j-k];
        f[i][j]=maxl;
    }
    printf("%d\n",f[n][m]);//输出结果 
    print(n,m);//输出分配方案 
    return 0;
}