题解 P2466 【[SDOI2008]Sue的小球】

JRhdj · 2017-11-23 12:20:29 · 题解

可以用区间dp解决

用f[i][j]表示取从i到j的彩蛋并且停留在i所失去的最小价值

用g[i][j]表示取从i到j的彩蛋并且停留在j所失去的最小价值

那么最后的答案就是 总价值 - min(f[1][n], g[1][n])

这样子的话转移就很简单了 细节看代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 1005;
int f[M][M], g[M][M], n, x0, pre[M], tc;
struct point
{
    int x, y, v;
}w[M];
bool cmp(point a, point b)
{
    return a.x < b.x;
}
int q(int l, int r)
{
    return pre[r] - pre[l-1];
}
int main()
{
    memset(f, 0x3f, sizeof f); memset(g, 0x3f, sizeof g);
    scanf("%d%d", &n, &x0);
    for(int i=1; i<=n; ++i) scanf("%d", &w[i].x);
    for(int i=1; i<=n; ++i) scanf("%d", &w[i].y), tc+=w[i].y;
    for(int i=1; i<=n; ++i) scanf("%d", &w[i].v);
    w[++n] = (point){x0, 0, 0};
    sort(w+1, w+n+1, cmp);
    for(int i=1; i<=n; ++i) pre[i] = pre[i-1] + w[i].v;
    for(int i=1; i<=n; ++i) if(w[i].x == x0 && w[i].v == 0) f[i][i]=0, g[i][i]=0;
    for(int k=1; k<n; ++k) for(int i=1; i<=n; ++i)
    {
        int j = i+k;
        if(j>n) break;
        f[i][j] = min(f[i][j], f[i+1][j]+(w[i+1].x-w[i].x)*(q(1, i)+q(j+1, n)));
        f[i][j] = min(f[i][j], g[i+1][j]+(w[j].x-w[i].x)*(q(1, i)+q(j+1, n)));
        g[i][j] = min(g[i][j], g[i][j-1]+(w[j].x-w[j-1].x)*(q(1, i-1)+q(j, n)));
        g[i][j] = min(g[i][j], f[i][j-1]+(w[j].x-w[i].x)*(q(1, i-1)+q(j, n)));
    }
    printf("%.3f\n", (tc-min(f[1][n], g[1][n]))/1000.0);
    return 0;
}