解法 状態が(場所, 最後に使ったカード)のdp ソースコード int min_ascending(const int* c, int n) { const int inf = ten(8); int dp[3 * ten(4) + 100][3]; // (pos, last card) erep(i, n) rep(j, 3) dp[i][j] = inf; dp[0][0] = 0; rep(i, n) rep(j, 3)…

bfs ソースコード int main() { int m; scanf("%d", &m); const int inf = ten(4); int dest_time[333][333]; const int w = 333, h = 333; rep(i, h) rep(j, w) dest_time[i][j] = inf; while (m--) { int x, y, t; scanf("%d%d%d", &x, &y, &t); chmin(des…

全ての組みを全探索 ソースコード int main() { int n, x[222], y[222]; scanf("%d", &n); rep(i, n) scanf("%d%d", x + i, y + i); set<pint> slope; rep(i, n) rep(j, i) { int dx = x[i] - x[j], dy = y[i] - y[j]; int g = __gcd(dx, dy); dx /= g, dy /= g; s</pint>…

解法 簡単のために与えられる区間[s, e]で重なっているものは1つの区間とします (s, e)にはスプリンクラーの範囲の端は置けませんまず始めに思いつく解法は以下のようなdpです [0, i]までスプリンクラーでカバーするときの最小値 dp[i] = min{dp[j] + 1 ; i …