https://beta.atcoder.jp/contests/arc085/tasks/arc085_d
配るDPともらうDPでわけわかんなくなってしまった…。
配るDPは操作を考えて、1手進めるとどこに遷移するかを考えるのが基本となります。
対して、もらうDPは漸化式を立ててからメモ化再帰に持っていく感じで、1手すすめるとかそういう考え方はあまりしないです。
今回のはdp(i,j):=[i,j)まで1が連続しているとしてiまでのハミング距離の差、と定義すると、
iをi+1に持っていくのを1手として遷移を考えるっていう感じになります。するといい感じにsegtreeが使えてO(NlogN)となります。
でもDPを考察する際はやっぱり小さい問題から簡単な遷移で大きな問題を解けないか考えてみて、操作についてはそのあとコードに落とす際に考えればいいかなと思いました。
int N, Q; int B[MAX_N]; vector<int> L[MAX_N]; segtree seg; bool used[MAX_N]; ll bitmin(ll a, ll b) { return -a + min(a, b); } void solve() { cin >> N; rep(i, 0, N) { cin >> B[i]; } cin >> Q; rep(i, 0, Q) { int a, b; cin >> a >> b; a--; L[a].pb(b); } seg.init(N + 1); rep(i, 0, sz(L[0])) { int v = L[0][i]; used[v] = true; } rep(i, 0, N + 1) { if(used[i] || !i) continue; seg.update(i, i + 1, N); } rep(i, 1, N + 1) { seg.update(i, N + 1, (1 != B[i - 1])); int tv = seg.get(i - 1, i).v; seg.update(i, i + 1, bitmin(seg.get(i, i + 1).v, tv + (0 != B[i - 1]))); rep(j, 0, sz(L[i])) { int to = L[i][j]; seg.update(to, to + 1, bitmin(seg.get(to, to + 1).v, seg.get(i, to + 1).v)); } } cout << seg.get(N, N + 1) << "\n"; }