AtCoder Beginner Contest 017 D サプリメント
考察
部分点まで自力で行けたけど、満点解法は解説を見ながら、AC。
解法としてはしゃくとり法をしつつ、DPをしていく。
dp[i] = i番目のサプリメントまでを見た時の摂取方法の組み合わせ
dp[i] := dp[i - 1] + dp[i - 2] + ... + dp[k]
kはf[j + 1],f[j + 2] ,...f[i]までのサプリメントが一日で食べられるような最小のjの値。
正直、未だにdpの遷移が良く分かってない。
参考:
AtCoder Beginner Contest 017 解説
AtCoder Beginner Contest #017 D問題 - サプリメント - ゲームにっき(仮)別館(仮)
AtCoder Beginner Contest #017 - hirokazu1020の日記
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { final static int MOD = (int)1e9 + 7; int N,M; int[] f; int[] dp; public void solve() { N = nextInt(); M = nextInt(); f = new int[N]; /* * dp[i] = dp[i - 1] + dp[i - 2] + ... dp[k] * kはf[j + 1],f[j + 2],...f[k]が一日に食べられるような最小なj。 */ dp = new int[N + 1]; for(int i = 0;i < N;i++){ f[i] = nextInt() - 1; } dp[0] = 1; //しゃくとりの区間内のサプリメントの味ごとの個数 int[] num = new int[M]; int left = 0; int sum = dp[0]; for(int i = 0;i < N;i++){ num[f[i]]++; //区間内に含まれる同じサプリメントの味の個数が1つになるまで左端を縮める while(num[f[i]] > 1){ num[f[left]]--; sum -= dp[left]; if(sum < 0)sum += MOD; sum %= MOD; left++; } dp[i + 1] = sum; out.println(dp[i + 1]); sum += dp[i + 1]; sum %= MOD; } out.println(dp[N]); } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }