信息学奥赛一本通T1266 -机器分配

解题思路:背包问题， 分配机器的数量， 使用ans数组记录第i个工厂在最大值所使用的机器数量j-k

注意事项:输出时注意顺序

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e1 + 10;
int a[N][N],n,m,f[N][N],ans[N][N],res[N];

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++){
			cin >> a[i][j];
		}
		
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			for(int k = 0; k <= j; k ++){
				if(f[i][j] < f[i-1][k] + a[i][j-k]){
					f[i][j] = f[i-1][k] + a[i][j-k];
					ans[i][j] = j - k;
				}
			}
	cout << f[n][m] << endl;
	int i = n, j = m, k = n;
	while(i){
		res[k--] = ans[i][j];
		j -= ans[i][j];
		i --;
	}
	for(int i = 1; i <= n; i ++) cout << i << ' ' <<res[i] << endl;
	return 0;
}