题目背景
无
题目描述
总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。
输入输出格式
输入格式：
第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。
接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。
输出格式：
第1行为最大盈利值
第2到第n为第i分公司分x台
输入输出样例
输入样例#1：
3 3
30 40 50
20 30 50
20 25 30
输出样例#1：
70
1 1
2 1
3 1
普通的DP，只是需要记录路径。
题目中没有说明，实际路径要输出字典序最大的那个。
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 int read(){ 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int pt[30][30]; 15 int f[30][30]; 16 int mp[30][30]; 17 void find(int i,int j){ 18 if(!i)return; 19 for(int k=j;k>=0;k--){ 20 if(f[i][j]==f[i-1][j-k]+mp[i][k]){ 21 find(i-1,j-k); 22 printf("%d %d ",i,k); 23 break; 24 } 25 } 26 return; 27 } 28 int main(){ 29 int i,j; 30 int n,m; 31 n=read();m=read(); 32 for(i=1;i<=n;i++) 33 for(j=1;j<=m;j++) 34 mp[i][j]=read(); 35 for(i=1;i<=n;i++) 36 for(j=0;j<=m;j++){ 37 for(int k=0;k<=j;k++){ 38 f[i][j]=max(f[i][j],f[i-1][j-k]+mp[i][k]); 39 } 40 } 41 printf("%d ",f[n][m]); 42 find(n,m); 43 return 0; 44 }