13162번: Flowey's Love

https://www.acmicpc.net/problem/13162

알갱이들이 직선 방향으로 움직일 때 주어진 구역 안에서 돌아다니며 모을 수 있는 최대 알갱이 수를 구하는 문제이다.

대충보면 TSP 이기 때문에 다항시간 안에 풀기 힘들다는 것을 알 수 있다. 주어진 n이 작으므로 모든 상태를 따져보는 DP로 해결한다.
알갱이를 최대한 많이 모으는 방법은 알갱이를 최대한 빠르게 모으는 방법이기도하다. 이에 따라 dp를 다음과 같이 정의한다.
dp[i][j]: 모은 알갱이의 집합이 i이고 영혼이 알갱이 j에 위치해 있을 때 걸리는 최소 시간
dp[i][j] = min(dp[i - j][k] + (dp[i - j][k]시간이 흐른 후 k->j로 가는데 걸리는 최소 시간) : k$\in$i)
* i-j는 집합 i에서 j를 제외함을 의미함.

문제에서는 영혼이 돌아다닐 수 있는 구역이 제한되어 있기 때문에 이를 고려해야 한다. 자세한 구현은 아래 소스를 참고하자.

시간복잡도는 $O(n^2 * 2^n)$

#include<cstdio>
#include<algorithm>
#define eps(u,v) (abs((u)-(v))<1e-9)
#define cmp(u,v) (u<v || eps(u,v))
using namespace std;
int n, xm, ym, res;
double sx[19], sy[19], dp[1 << 19][19], vx[19], vy[19], lt[19];
double f(double x, double y, int h, double t) {
    double xi = sx[h] + vx[h] * t - x, yi = sy[h] + vy[h] * t - y;
    if (eps(xi, 0) && eps(yi, 0)) return 0;
    double a = (xi*vx[h] + yi*vy[h]) * 2, b = xi*xi + yi*yi;
    return eps(a, 0) || cmp(0, b / a) ? 1e5 : -b / a;
}
int main() {
    scanf("%d%d%d", &n, &xm, &ym); n++;
    for (int i = 1, ex, ey; i < n; i++) {
        scanf("%lf%lf%d%d", sx + i, sy + i, &ex, &ey);
        double d = hypot(ex - sx[i], ey - sy[i]);
        vx[i] = (ex - sx[i]) / d;
        vy[i] = (ey - sy[i]) / d;
        lt[i] = max(eps(vx[i], 0) ? 0 : min((-xm - sx[i]) / vx[i], (xm - sx[i]) / vx[i]),
            eps(vy[i], 0) ? 0 : min((-ym - sy[i]) / vy[i], (ym - sy[i]) / vy[i]));
    }
    fill(dp[0], dp[1 << n], 1e5);
    dp[1][0] = 0;
    for (int i = 1; i < 1 << n; i++) {
        int bt = 0;
        for (int j = i; j; j &= j - 1) bt++;
        for (int j = 0; j < n; j++) if (1 << j&i) {
            for (int k = 0; k < n; k++) if (1 << k&i &&j^k) {
                double t = dp[i ^ 1 << j][k], ret = max(t + f(sx[k] + vx[k] * t, sy[k] + vy[k] * t, j, t), lt[j]),
                    tx = sx[j] + vx[j] * ret, ty = sy[j] + vy[j] * ret;
                if (cmp(-xm, tx) && cmp(tx, xm) && cmp(-ym, ty) && cmp(ty, ym)) dp[i][j] = min(dp[i][j], ret);
            }
            if (dp[i][j] < 1e4) res = max(res, bt - 1);
        }
    }
    printf("%d", res);
    return 0;
}