AcWing 1013. 机器分配(Java模板写法)
原题链接
简单
作者:
执梗
,
2022-05-14 17:01:04
,
所有人可见
,
阅读 127
import java.util.Scanner;
public class Main {
static int N=20;
static int n,m;
static int[][] a=new int[N][N];
//只考虑前i家公司,分配j台机器能获得的最大价值
static int[][] f=new int[N][N];
static int[] way=new int[N];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
a[i][j]=sc.nextInt();
}
}
//考虑前i家公司
for (int i = 1; i <=n; i++) {
//总共有j台机器
for (int j = 0; j <=m; j++) {
//考虑第i家选多少台机器
for (int k = 0; k<=j; k++) {
f[i][j]=Math.max(f[i][j],f[i-1][j-k]+a[i][k]);
}
}
}
System.out.println(f[n][m]);
//倒推求集体方案
int j=m;
for (int i = n; i >0; i--) {
for (int k = 0; k <=j; k++) {
if (f[i][j]==f[i-1][j-k]+a[i][k]){
way[i]=k;
j-=k;
break;
}
}
}
for (int i = 1; i <=n; i++) {
System.out.println(i+" "+way[i]);
}
}
}