首页 > 代码库 > 机器分配
机器分配
PS：洛古P2066
思路：
f[i][j]表示前i个公司分配j台机器能得到的最大收益
c[i][j]表示第i个公司分配j台机器能得到的最大收益（注意i和j的区别）
这样就可以从上往下推
第三重循环控制变量k为前i-1个公司分配的机器数，
那么显然第i各公司能分到j-k台机器
转移：f[i][j]=max(f[i][j],f[i-1][k]+c[i][j-k])
关于输出第几个公司分几台机器，
我们发现在动规里很难记录状态，所以采取递归搜索的方式
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int c[11][16],f[11][16],maxl; 5 int max(int,int); 6 void find(int,int); 7 int main(){ 8 int n,m; 9 scanf("%d %d",&n,&m);10 for (int i=1;i<=n;i++)11 for (int j=1;j<=m;j++)12 scanf("%d",&c[i][j]);13 for (int i=1;i<=n;i++)14 for (int j=1;j<=m;j++)15 for (int k=0;k<=j;k++)16 f[i][j]=max(f[i][j],f[i-1][k]+c[i][j-k]);17 printf("%d\n",f[n][m]);18 maxl=f[n][m];19 find(n,m);20 return 0;21 }22 int max(int x,int y){23 return x>y?x:y;24 }25 void find(int i,int j){26 if (i==0) return;27 for (int k=0;k<=j;k++)28 if (maxl==f[i-1][k]+c[i][j-k]){29 maxl=f[i-1][k];30 find(i-1,k);31 printf("%d %d\n",i,j-k);32 break;33 }34 }
机器分配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。