4385951_mle.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		Scanner in = new Scanner(System.in);
		int c, n;
		int[][] mark = new int[100001][11];
		boolean[] dp = new boolean[100001];

		while (in.hasNext()) {
			c = in.nextInt();
			n = in.nextInt();
			int[] v = new int[n];
			int[] d = new int[n];
			
			for (int i = 0; i < n; i++) {
				v[i] = in.nextInt();
				d[i] = in.nextInt();
			}
			for (int i = 0; i <= c; i++) {
				dp[i] = false;
				for (int j = 0; j < n; j++) {
					mark[i][j] = 0;
				}
			}
			dp[0] = true;
			for (int i = 1; i <= c; i++) {
				for (int j = 0; j < n; j++) {
					int t = i - v[j];
					if (t < 0 || d[j] <= mark[t][j] || !dp[t]) {
						continue;
					}
					dp[i] = true;
					for (int k = 0; k < n; k++) {
						mark[i][k] = mark[t][k];
					}
					mark[i][j]++;
				}
			}
			int ans = 0;
			for (int i = 1; i <= c; i++) {
				if (dp[i]) {
					ans = i;
				}
			}
			System.out.println(ans);
		}
	}
}