http://codeforces.com/contest/983
A
えーABCの中で一番手間取った。QとBの最大公約数gをとってQをgで割ることを繰り返す。こういうの苦手。
B
dpしてまたdp
C
dp[i][j][k][l][m][n]:=i番目の人までみて、場所jにいる。エレベーターに乗っている人はk,l,m,nである時の最小コストとやると、2*10^8となって辛いです。しかし、i番目の人が乗った場合行き先がbiの人が必ずいるので、それを利用するとnを10試す必要がなくなって2で大丈夫になります。これで2*10^7*2で通ります。2*10^8/(4!)が通ってしまうのは少し解せない…。コードがだいぶエグい。
int N; int A[MAX_N], B[MAX_N]; int dp[2010][9][10][10][10][2]; //i,at j,floor at; k, l, m floor to visit, B[i], visited? void solve() { cin >> N; rep(i, 0, N) { cin >> A[i] >> B[i]; A[i]--; B[i]--; } rep(i, 0, N + 1) { rep(j, 0, 9) { rep(k, 0, 10) { rep(l, 0, 10) { rep(m, 0, 10) { rep(n, 0, 2) { dp[i][j][k][l][m][n] = inf; } } } } } } dp[0][A[0]][9][9][9][0] = A[0]; //i, j, k, l, m, n rep(i, 0, N) { rep(k, 0, 10) { rep(l, 0, 10) { rep(m, 0, 10) { rep(n, 0, 2) { rep(j, 0, 9) { if(dp[i][j][k][l][m][n] == inf) continue; // debug(i, j, k, l, m, n); if(k == 9) { //visited MIN(dp[i + 1][A[i + 1]][B[i]][l][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j)); } else { MIN(dp[i][k][9][l][m][n], dp[i][j][k][l][m][n] + abs(k - j)); } if(l == 9) { MIN(dp[i + 1][A[i + 1]][k][B[i]][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j)); } else { MIN(dp[i][l][k][9][m][n], dp[i][j][k][l][m][n] + abs(l - j)); } if(m == 9) { MIN(dp[i + 1][A[i + 1]][k][l][B[i]][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j)); } else { MIN(dp[i][m][k][l][9][n], dp[i][j][k][l][m][n] + abs(m - j)); } if(n == 1) { //visited MIN(dp[i + 1][A[i + 1]][k][l][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j)); } else { MIN(dp[i][B[i]][k][l][m][1], dp[i][j][k][l][m][n] + abs(B[i] - j)); } } } } } } } int res = inf; rep(i, 0, 9) { MIN(res, dp[N - 1][i][9][9][9][1]); } cout << res + 2 * N << "\n"; }