レストラン(ダイナミックプランニング)

あるレストランにはnつのテーブルがあり、各テーブルにはパラメータがあります.aが収容できる最大人数です.mロットのお客様がいて、各ロットのお客様には2つのパラメータがあります:bは人数で、cは消費金額を予想します.相席が許可されていない場合は、アルゴリズムを実装して一部のお客様を選択し、総予想消費金額が最大になるようにしてください.
入力にはm+2行が含まれます.
1行目の2つの整数n(1<=n<=50000)、m(1<=m<=50000)
第2の動作n個のパラメータa、すなわち、各テーブルに収容可能な最大人数は、32ビットintの範囲内でスペースで区切られる.
次にm行、各行に2つのパラメータb,cを示す.第i陣の客の人数と予想消費金額をそれぞれ表し、スペースで区切られ、範囲は32位の範囲内である.
最大の総予想消費金額を示す整数を出力
入力例:
3 5
2 4 2
1 3
3 5 
3 7
5 
1 10
入力:
20

import java.util.*;

public class Main

{
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			int[] c = new int[m];
			int[] w = new int[n];
			for (int i = 0; i < m; i++) {
				c[i] = sc.nextInt();
			}
			int[] v = new int[n];

			for (int i = 0; i < n; i++) {
				w[i] = sc.nextInt();
				v[i] = sc.nextInt();
			}

			int[][] b = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (w[i] < c[j]) {
						b[i][j] = v[i];
					} else {
						b[i][j] = 0;
					}
				}
			}
			/*
			 * int[][] b = {{3,3,3}, {0,5,0}, {0,7,0}, {0,0,0}, {10,10,10}};
			 */

			int row = b.length;
			int column = b[0].length;
			int[][] result = new int[row][column];
			Set set = new HashSet();
			ArrayList> list = new ArrayList>();
			for (int i = 0; i < row; i++) {
				list.add(new HashSet());
			}
			int[][] flag = new int[row][column];
			for (int i = 0; i < row; i++) {
				result[i][0] = b[i][0];
				list.get(i).add(i);
				flag[i][0] = i;
			}
			for (int t = 1; t < column; t++) {
				for (int j = 0; j < row; j++) {
					int max = 0;
					int maxflag = 0;
					for (int i = 0; i < row; i++) {
						if (result[j][t - 1] + b[i][t] >= max && !list.get(j).contains(i)) {
							max = result[j][t - 1] + b[i][t];
							maxflag = i;
						}
					}
					flag[j][t] = maxflag;
					result[j][t] = max;
					list.get(j).add(maxflag);
				}
			}
			int rs = 0;
			int k = 0;
			for (int i = 0; i < row; i++) {
				if (result[i][column - 1] > rs) {
					rs = result[i][column - 1];
					k = i;
				}
			}
			System.out.println(rs);
			for (int i = 0; i < column; i++) {
				System.out.print(flag[k][i] + "-->");

			}
		}
	}