Luogu p2466 [sdoi2008] Sue's small ball solution

Luogu P2466 [SDOI2008] Sue The ball of Answer key

Topic link ：P2466 [SDOI2008] Sue The ball of

The question ：

Sue and Sandy Recently, I fell in love with a computer game , The story of this game is in the beautiful, mysterious and exciting sea ,Sue There is a small and light boat . However ,Sue My goal is not to be a pirate , It's about collecting eggs floating in the air ,Sue There is a secret weapon , As long as she rowed the boat directly under a colored egg , Then you can collect the eggs in an instant by using secret weapons . However , Colored eggs have a charm value , This charm value will decrease with the time the colored egg lands in the air ,Sue To get more points , You must try to collect the eggs when the charm value is high , And if an egg falls into the sea , Its charm value will become a negative number , But it doesn't affect Sue The interest of , Because every egg is different ,Sue Hope to collect all the eggs .

However Sandy There is no Sue So romantic ,Sandy Hope to get as many scores as possible , To solve this problem , He first abstracted the game into the following model ：

Think of the sea as $x$ Axis , With Sue The initial position is used as the coordinate origin to establish a vertical plane rectangular coordinate system .

At first there was $N$ An egg , For the first $i$ An egg , His initial position is in integer coordinates $(x_i,y_i)$ Express , When the game starts , Its uniform velocity along $y$ The shaft falls in the negative direction , Speed is $v_i$ Unit distance / Unit time .Sue The initial position of the is $(x_0,0)$,Sue You can go along $x$ The axis moves in the positive or negative direction ,Sue What's your speed $1$ Unit distance / Unit time , Using secret weapons to get a painted egg is instantaneous , Score for the current egg $y$ One thousandth of a coordinate .

Now? ,Sue and Sandy Please help me , In order to satisfy the Sue and Sandy Respective goals , You decide to collect all the eggs , Get the highest score .

about $100\%$ The data of ,$-10^4\le x_i,y_i,v_i\le 10^4$,$N\le 1000$

First, press the eggs $x$ Sort

Because you can walk left and right , It can be thought that this is an interval dp

set up $f_{0/1,i,j}$ Indicates the interval $[i,j]$ The minimum cost after all the eggs are collected （ cost ）,0/1 It means that at this time $i$ still $j$

Transfer equation ？

be aware The current decision will be affected by the previous decision , That is to say The present moment is not clear to us

Consider adding one dimension ？ That is the solution of violence

So how to deal with this moment ？

Let's change the question just now ,

“ The current decision will be affected by the previous decision ”

let me put it another way , Namely The current decision will affect the subsequent decision

That is to say , The present moment will affect the value of the item when it is transferred later

Consider every decision , Let's take the subsequent costs into account

set up $w_{i,j}$ Indicates the interval $[i,j]$ The impact on subsequent decisions （ cost ）, It's not hard to find out
$$w_{i,j}=\sum _{i=0}^n{v}_i-\sum _{k=i}^j{v}_k$$
Obviously you can prefix and optimize

Of course, the most important thing is , We can It's easy to The transfer equation is derived
$$\begin{gathered} f_{0,i,j}=\min \left\{f_{0,i+1,j}+(x_{i+1}-x_i)\times (S_i+S_n-S_j),f_{1,i+1,j}+(x_j-x_i)\times (S_i+S_n-S_j)\right\} \\ {f}_{1,i,j}=\min \left\{f_{0,i,j-1}+(x_j-x_i)\times (S_{i-1}+S_n-S_{j-1}),f_{1,i,j-1}+(x_j-x_{j-1})\times (S_{i-1}+S_n-S-j-1)\right\} \end{gathered}$$
among $S_k={\sum }_{i=1}^k{v}_k$

Time complexity $O(n^2)$

The answer is $\sum y_i-\min \left\{f_{0,1,n},f_{1,1,n}\right\}$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)

int n,x0,f0[N][N],f1[N][N];
struct node{
    int x,y,v;}a[N];
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> x0;
    for(int i=1; i<=n; i++) cin >> a[i].x;
    for(int i=1; i<=n; i++) cin >> a[i].y;
    for(int i=1; i<=n; i++) cin >> a[i].v;
    a[++n].x=x0;
    sort(a+1,a+1+n,[](node a,node b){
    return a.x<b.x;});
    memset(f0,0x3f,sizeof(f0));memset(f1,0x3f,sizeof(f1));
    for(int i=1; i<=n; i++)
        if(a[i].x==x0){
    f0[i][i]=f1[i][i]=0;}
    for(int i=1; i<=n; i++) a[i].v+=a[i-1].v;
    for(int len=2; len<=n; len++)
        for(int i=1,j=i+len-1; j<=n; i++,j++)
        {
    
            f0[i][j]=min(f0[i+1][j]+(a[i+1].x-a[i].x)*(a[i].v+a[n].v-a[j].v),
                         f1[i+1][j]+(a[j].x-a[i].x)*(a[i].v+a[n].v-a[j].v));
            f1[i][j]=min(f0[i][j-1]+(a[j].x-a[i].x)*(a[i-1].v+a[n].v-a[j-1].v),
                         f1[i][j-1]+(a[j].x-a[j-1].x)*(a[i-1].v+a[n].v-a[j-1].v));
        }
    int sum=0;
    for(int i=1; i<=n; i++) sum+=a[i].y;
    cout << fixed << setprecision(3);
    cout << ((sum-min(f0[1][n],f1[1][n]))/1000.0) << '\n';
    return 0;
}

reference

[1] https://www.luogu.com.cn/blog/Bartholomew/solution-p2466

Reprint please explain the source