http://arc073.contest.atcoder.jp/tasks/arc073_ddp高速化。dp[i][j]:=(i番目のqueryまで処理して、2点の座標がx[i]とjの時の最小値)とする。 するとdp[i][j]+jとdp[i][j]-jの値についてrange_sumとrange_minが出来れば高速に更新できる。2つsegtreeを持た…

http://arc074.contest.atcoder.jp/tasks/arc074_dflow。行と列を代表する頂点を用意してうまく辺を張ると、辺の本数がO(H*W)になって十分高速。 int H, W; string S[MAX_N]; void solve() { cin >> H >> W; int s, t; rep(i, 0, H) { cin >> S[i]; rep(j, 0…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 monge(もんじゅ)dp。http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915 と http://sssslide.com/www.slideshare.net/ikumihide/ss-50881829 を参考にした。単調性が本質で、それを…