VvyLw's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub

:warning: Java/library/other/DP.java

Depends on

Required by

Code

package library.other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

import library.core.Utility;
import library.ds.pair.IntPair;

/**
 * DPを使った便利メソッドまとめ
 */
public final class DP {
	/**
	 * 01ナップザック
	 * 重さa_i, 価値v_iであるようなn個の品物があり、重さの和がw以下となるように選ぶときの価値の最大値を求める
	 * @param a
	 * @param v
	 * @param w
	 * @return dpの最大値
	 * @apiNote O(NW)
	 * @see <a href="https://ei1333.github.io/library/dp/knapsack-01.hpp">参考元</a>
	 */
	public static final long knapsack01(final int[] a, final long[] v, final int w) {
		final int n = a.length;
		final long[] dp = new long[w + 1];
		Arrays.fill(dp, Long.MIN_VALUE);
		dp[0] = 0;
		for(int i = 0; i < n; i++) {
			for(int j = w; j >= a[i]; j--) {
				if(dp[j - a[i]] != Long.MIN_VALUE) {
					if(dp[j - a[i]] + v[i] > dp[j]) {
						dp[j] = dp[j - a[i]] + v[i];
					}
				}
			}
		}
		return Utility.max(dp);
	}
	/**
	 * 01ナップザック
	 * 重さw_i, 価値v_iであるようなn個の品物があり、重さの和がw以下となるように選ぶときの価値の最大値を求める
	 * @param a
	 * @param v
	 * @param w
	 * @return dpの最大値
	 * @apiNote O(N sum(v))
	 * @see <a href="https://ei1333.github.io/library/dp/knapsack-01-2.hpp">参考元</a>
	 */
	public static final int knapsack01(final long[] a, final int[] v, final long w) {
		final int n = a.length;
		final int s = (int) Utility.sum(v);
		final long[] dp = new long[s + 1];
		Arrays.fill(dp, w + 1);
		dp[0] = 0;
		for(int i = 0; i < n; i++) {
			for(int j = s; j >= v[i]; j--) {
				dp[j] = Math.min(dp[j], dp[j - v[i]] + a[i]);
			}
		}
		int res = 0;
		for(int i = 0; i <= s; i++) {
			if(dp[i] <= w) {
				res = i;
			}
		}
		return res;
	}
	private static final long[] knapsack(final int[] a, final long[] v, final int[] m, final int w, final boolean less) {
		final int n = a.length;
		final long[] dp = new long[w + 1], deqv = new long[w + 1];
		Arrays.fill(dp, Long.MIN_VALUE);
		dp[0] = 0;
		final int[] deq = new int[w + 1];
		for(int i = 0; i < n; ++i) {
			if(a[i] == 0) {
				for(int j = 0; j <= w; ++j) {
					if(dp[j] != Long.MIN_VALUE && (less ? dp[j] + v[i] * m[i] < dp[j] : dp[j] + v[i] * m[i] > dp[j])) {
						dp[j] = dp[j] + v[i] * m[i];
					}
				}
			} else {
				for(int k = 0; k < a[i]; ++k) {
					int s = 0, t = 0;
					for(int j = 0; a[i] * j + k <= w; ++j) {
						if(dp[a[i] * j + k] != Long.MIN_VALUE) {
							final long val = dp[a[i] * j + k] - j * v[i];
							while(s < t && (less ? val < deqv[t - 1] : val > deqv[t - 1])) {
								t--;
							}
							deq[t] = j;
							deqv[t++] = val;
						}
						if(s < t) {
							dp[j * a[i] + k] = deqv[s] + j * v[i];
							if(deq[s] == j - m[i]) {
								s++;
							}
						}
					}
				}
			}
		}
		return dp;
	}
	/**
	 * 個数制限つきナップザック
	 * 重さw_i, 価値v_iであるようなn種類の品物があり、i番目の品物はm_i個まで選ぶことができる
	 * 重さの和がw以下となるように選ぶときの価値の最大値を求める
	 * @param a
	 * @param v
	 * @param m
	 * @param w
	 * @return dpの最大値
	 * @apiNote O(NW)
	 * @see <a href="https://ei1333.github.io/library/dp/knapsack-limitations.hpp">参考元</a>
	 */
	public static final long knapsack(final int[] a, final long[] v, final int[] m, final int w){ return Utility.max(knapsack(a, v, m, w, false)); }
	/**
	 * 個数制限つきナップザック
	 * 重さw_i, 価値v_iであるようなn種類の品物があり、i番目の品物はm_i個まで選ぶことができる
	 * 重さの和がw以下となるように選ぶときの価値の最大値を求める
	 * @param a
	 * @param v
	 * @param m
	 * @param w
	 * @return dpの最大値
	 * @apiNote O((N max(v))^2)
	 * @see <a href="https://ei1333.github.io/library/dp/knapsack-limitations-2.hpp">参考元</a>
	 */
	public static final long knapsack(final long[] a, final int[] v, final long[] m, final long w) {
		final int n = a.length;
		final int max = Utility.max(v);
		if(max == 0) {
			return 0;
		}
		final int[] ma = new int[n];
		final long[] mb = new long[n];
		for(int i = 0; i < n; i++) {
			ma[i] = (int) Math.min(m[i], max - 1);
			mb[i] = m[i] - ma[i];
		}
		int sum = 0;
		for(int i = 0; i < n; ++i) {
			sum += ma[i] * v[i];
		}
		final long[] dp = knapsack(v, a, ma, sum, true);
		final int[] id = Utility.iota(n).boxed().sorted((i, j) -> -Long.compare(v[i] * a[j], v[j] * a[i])).mapToInt(i -> i).toArray();
		long res = 0;
		for(int i = 0; i < dp.length; ++i) {
			if(dp[i] > w || dp[i] == Long.MIN_VALUE) {
				continue;
			}
			long rest = w - dp[i], cost = i;
			for(final int j: id) {
				final long get = Math.min(mb[j], rest / a[j]);
				if(get <= 0) {
					continue;
				}
				cost += get * v[j];
				rest -= get * a[j];
			}
			res = Math.max(res, cost);
		}
		return res;
	}
	/**
	 * 個数制限なしナップサック
	 * 重さw_i, 価値v_iであるようなn種類の品物があり、重さの和がw以下となるように選ぶときの価値の最大値を求める
	 * @param a
	 * @param v
	 * @param w
	 * @return dpの最大値
	 * @apiNote O(NW)
	 * @see <a href="https://ei1333.github.io/library/dp/knapsack.hpp">参考元</a>
	 */
	public static final long knapsack(final int[] a, final long[] v, final int w) {
		final int n = a.length;
		final long[] dp = new long[w + 1];
		Arrays.fill(dp, Long.MIN_VALUE);
		dp[0] = 0;
		for(int i = 0; i < n; i++) {
			for(int j = a[i]; j <= w; j++) {
				if(dp[j - a[i]] != Long.MIN_VALUE) {
					if(dp[j - a[i]] + v[i] > dp[j]) {
						dp[j] = dp[j - a[i]] + v[i];
					}
				}
			}
		}
		return Utility.max(dp);
	}
	/**
	 * ヒストグラムの最大長方形の面積を返す
	 * @param a
	 * @return ヒストグラムの最大長方形の面積
	 * @apiNote O(N)
	 * @see <a href="https://ei1333.github.io/library/dp/largest-rectangle.hpp">参考元</a>
	 */
	public static final long maxRectangle(final int[] a) {
		final Stack<Integer> sk = new Stack<>();
		final long[] h = new long[a.length + 1];
		for(int i = 0; i < a.length; ++i) {
			h[i] = a[i];
		}
		final int[] l = new int[h.length];
		long res = 0;
		for(int i = 0; i < h.length; i++) {
			while(!sk.isEmpty() && h[sk.peek()] >= h[i]) {
				res = Math.max(res, (i - l[sk.peek()] - 1) * h[sk.pop()]);
			}
			l[i] = sk.isEmpty() ? -1 : sk.peek();
			sk.add(i);
		}
		return res;
	}
	/**
	 * ヒストグラムの最大長方形の面積を返す
	 * @param a
	 * @return ヒストグラムの最大長方形の面積
	 * @apiNote O(N)
	 * @see <a href="https://ei1333.github.io/library/dp/largest-rectangle.hpp">参考元</a>
	 */
	public static final long maxRectangle(final long[] a) {
		final Stack<Integer> sk = new Stack<>();
		final long[] h = Arrays.copyOf(a, a.length + 1);
		final int[] l = new int[h.length];
		long res = 0;
		for(int i = 0; i < h.length; i++) {
			while(!sk.isEmpty() && h[sk.peek()] >= h[i]) {
				res = Math.max(res, (i - l[sk.peek()] - 1) * h[sk.pop()]);
			}
			l[i] = sk.isEmpty() ? -1 : sk.peek();
			sk.add(i);
		}
		return res;
	}
	/**
	 * Longest Common Subsequence
	 * @param s
	 * @param t
	 * @return 最長共通部分列の長さ
	 * @see <a href="https://maku.blog/p/a3jyhwd/">参考元</a>
	 */
	public static final int lcs(final String s, final String t) {
		final int n = s.length();
		final int[] dp = new int[n + 1], ndp = new int[n + 1];
		for(int i = 0; i < t.length(); ++i) {
			for(int j = 0; j < n; ++j) {
				if(s.charAt(j) == t.charAt(i)) {
					ndp[j + 1] = dp[j] + 1;
				} else {
					ndp[j + 1] = Math.max(ndp[j], dp[j + 1]);
				}
			}
			Utility.swap(dp, ndp);
		}
		return dp[n];
	}
	/**
	 * 最長増加部分列(Longest Increasing Subsequence)
	 * @param a
	 * @return 最長増加部分列
	 * @see <a href="https://nyaannyaan.github.io/library/dp/longest-increasing-sequence.hpp">参考元</a>
	 * @apiNote Java21より前のVerの場合、getLastをget(dp.size() - 1)に変える
	 */
	public static final int[] lis(final int[] a) {
		final int n = a.length;
		List<IntPair> dp = new ArrayList<IntPair>();
		final int[] p = new int[n];
		Arrays.fill(p, -1);
		for(int i = 0; i < n; ++i) {
			final int id = Utility.lowerBound(dp, IntPair.of(a[i], -i));
			if(id != 0) {
				p[i] = -dp.get(id - 1).second.intValue();
			}
			if(id == dp.size()) {
				dp.add(IntPair.of(a[i], -i));
			} else {
				dp.set(id, IntPair.of(a[i], -i));
			}
		}
		final List<Integer> res = new ArrayList<Integer>();
		for(int i = -dp.getLast().second.intValue(); i != -1; i = p[i]) {
			res.add(i);
		}
		Collections.reverse(res);
		return res.stream().mapToInt(i -> i).toArray();
	}
	/**
	 * 最長増加部分列(Longest Increasing Subsequence)
	 * @param a
	 * @return 最長増加部分列
	 * @see <a href="https://nyaannyaan.github.io/library/dp/longest-increasing-sequence.hpp">参考元</a>
	 * @apiNote Java21より前のVerの場合、getLastをget(dp.size() - 1)に変える
	 */
	public static final int[] lis(final long[] a) {
		final int n = a.length;
		List<IntPair> dp = new ArrayList<IntPair>();
		final int[] p = new int[n];
		Arrays.fill(p, -1);
		for(int i = 0; i < n; ++i) {
			final int id = Utility.lowerBound(dp, IntPair.of(a[i], -i));
			if(id != 0) {
				p[i] = -dp.get(id - 1).second.intValue();
			}
			if(id == n) {
				dp.add(IntPair.of(a[i], -i));
			} else {
				dp.set(id, IntPair.of(a[i], -i));
			}
		}
		final List<Integer> res = new ArrayList<Integer>();
		for(int i = -dp.getLast().second.intValue(); i != -1; i = p[i]) {
			res.add(i);
		}
		Collections.reverse(res);
		return res.stream().mapToInt(i -> i).toArray();
	}
}
Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle
    raise RuntimeError('bundler is not specified: {}'.format(str(path)))
RuntimeError: bundler is not specified: Java/library/other/DP.java
Back to top page