P2066 机器分配

admin

https://www.luogu.org/problemnew/show/P2066

题目描述
总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

输入输出格式
输入格式：
第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。

接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。

输出格式：
第1行为最大盈利值

第2到第n为第i分公司分x台

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

输入输出样例
输入样例#1：
3 3
30 40 50
20 30 50
20 25 30
输出样例#1：
70
1 1
2 1
3 1

universehyf

1. #include<iostream>
   
2. using namespace std;
   
3. #define FOR(i,n,m) for(int i=n;i<=m;i++)
   
4. int a[3010][3010],f[3010][3010],g[3010][3010];
   
5. int n,m,t;
   
6. void dg(int x,int cc)
   
7. {
   
8.     if(x==1) {cout<<"1 "<<cc<<endl;;return;}
   
9.     dg(x-1,cc-g[x][cc]);
   
10.     cout<<x<<' '<<g[x][cc]<<endl;
    
11. }int main()
    
12. {
    
13.     ios::sync_with_stdio(false);
    
14.     cin>>n>>m;FOR(i,1,n) FOR(j,1,m) cin>>a[i][j];
    
15.     FOR(i,1,n) FOR(j,0,m){
    
16.         FOR(k,0,j) if(f[i-1][k]+a[i][j-k]>f[i][j]){
    
17.             f[i][j]=f[i-1][k]+a[i][j-k];
    
18.             g[i][j]=j-k;
    
19.         }
    
20.     }///cout<<n<<" "<<m<<endl;
    
21.     cout<<f[n][m]<<endl;dg(n,m);
    
22.     return 0;
    
23. }

复制代码