luoguP2466 [SDOI2008] 슈의 작은 공

이 문제는\(luoguP1220\) 가로등 끄기와 유사하지만 이 문제의 수익은 시간의 변화에 따라 달라집니다.
처음에 나는 3차원 (dp\), 즉 2차원 좌표, 1차원 시간에 대해 생각했다.
아쉽게도 공간이 터졌다.
그러나 시간은 선형이기 때문에 우리는 반대로 설정할 수 있다.
즉설\(dp[0/1][st][ed]\)는 좌표에 따라 정렬된 제\(st\)개의 알을 제\(ed\)개의 알로 처리한 후 남은 알에 미치는 영향을 나타낸다.
답은\(\sum^{n} {i=1}y[i]-\min(dp[0][1][n], dp[1][1][n])\이다.
전환이 일반 구간\(dp\) 소켓이 됩니다.\[\begin{align} dp[0][st][ed]=&min(dp[0][st][ed],min(\\&dp[0][st+1][ed]+(sum[n]+sum[st]-sum[ed])*(a[st + 1].x - a[st].x),\\&dp[1][st + 1][ed] + (sum[n] + sum[st] - sum[ed]) * (a[ed].x - a[st].x)));\\dp[1][st][ed]=&min(dp[1][st][ed],min(\\&dp[1][st][ed - 1] + (sum[n] + sum[st - 1] - sum[ed - 1]) * (a[ed].x - a[ed - 1].x),\\&dp[0][st][ed - 1] + (sum[n] + sum[st - 1] - sum[ed - 1]) * (a[ed].x - a[st].x)));\end{align}\]

#pragma GCC optimize(3)
#include
#define il inline
#define rg register
#define gi read
using namespace std;
const int O = 1010;
template
il TT read() {
    TT o = 0,fl = 1; char ch = getchar();
    while (!isdigit(ch) && ch != '-') ch = getchar();
    if (ch == '-') fl = -1, ch = getchar();
    while (isdigit(ch)) o = o * 10 + ch - '0', ch = getchar();
    return fl * o;
}
struct Data {
    int x, y, v;
    il bool operator < (Data rhs) const {
        return x < rhs.x;
    }
}a[O];
int n, St, sum[O], dp[2][O][O], Sum;
int main() {
    memset(dp, 63, sizeof dp);
    n = gi() + 1, a[1].x = St = gi();
    for (int i = 2; i <= n; ++i) a[i].x = gi();
    for (int i = 2; i <= n; ++i) a[i].y = gi(), Sum += a[i].y;
    for (int i = 2; i <= n; ++i) a[i].v = gi();
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i].v;
    for (int i = 1; i <= n; ++i)
        if (!a[i].v && a[i].x == St) {
            dp[0][i][i] = dp[1][i][i] = 0;
            break;
        }
    for (int len = 1; len < n; ++len)
        for (int st = 1; st + len <= n; ++st) {
            int ed = st + len;
            dp[0][st][ed] = min(dp[0][st][ed], min(dp[0][st + 1][ed] + (sum[n] + sum[st] - sum[ed]) * (a[st + 1].x - a[st].x), dp[1][st + 1][ed] + (sum[n] + sum[st] - sum[ed]) * (a[ed].x - a[st].x)));
            dp[1][st][ed] = min(dp[1][st][ed], min(dp[1][st][ed - 1] + (sum[n] + sum[st - 1] - sum[ed - 1]) * (a[ed].x - a[ed - 1].x), dp[0][st][ed - 1] + (sum[n] + sum[st - 1] - sum[ed - 1]) * (a[ed].x - a[st].x)));
        }
    printf("%.3lf
", (Sum - min(dp[1][1][n], dp[0][1][n])) / 1000.);
    return 0;
}