链接
P2466 [SDOI2008] Sue 的小球
思路
这题的难点在于：当前走一步所花的时间，不只影响当前要收集的彩蛋，还会让其它还没有收集到的彩蛋继续下降。所以不能简单贪心，需要用区间 DP 来处理。
先把所有彩蛋按 x 坐标排序。因为 Sue 一开始在 x0，每次只能沿着 x 轴左右移动，所以对于某一个已经连续处理过的区间，下一次只可能从这个区间的左端或右端继续扩展。
代码中没有直接把 x0 插入数组，而是找到第一个 x >= x0 的位置 begin，然后把 begin 左边的点接到数组后面：
for(int i=1;i<begin;i++)ets[i+n]=ets[i];
这样从 begin 到 begin+n-1 这一段，就形成了一个从起点右侧开始、再绕到左侧的环形序列。之后所有 DP 都在这一段长度为 n 的序列上进行。
设：
dp[0][l][r]
表示已经处理了当前序列中的区间 [l,r]，并且最后停在左端点 l 时，能得到的最大分数。
dp[1][l][r]
表示已经处理了当前序列中的区间 [l,r]，并且最后停在右端点 r 时，能得到的最大分数。
为了方便写数组，代码里真实下标 i,j 会减去 base=begin-1，变成 DP 下标 dpi,dpj。
初始化时，如果区间里只有一个彩蛋，那么不考虑起点到它的初始移动，先只记它本身的魅力值：
dp[0][dpi][dpj]=dp[1][dpi][dpj]=ets[i].y;
后面枚举区间长度 len，考虑把新区间的左端点或右端点加入进来。
如果当前要让状态停在左端点 i，那么上一步可能来自：
- 已经在
i+1。 - 已经在
j。
对应代码：
int a=dp[0][dpi+1][dpj]-abs(ets[i+1].x-ets[i].x)*(sumv[dpj]-sumv[dpi]);
int b=dp[1][dpi+1][dpj]-abs(ets[j].x-ets[i].x)*(sumv[dpj]-sumv[dpi]);
dp[0][dpi][dpj] = max(a,b)+dp[0][dpi][dpi];
这里减去的部分表示移动过程中产生的损失。sumv[dpj]-sumv[dpi] 是区间内已经会受到这次移动影响的速度和，距离乘速度和就是这一段移动造成的总分数下降。
同理，如果当前要让状态停在右端点 j，上一步可能来自：
- 已经在
i。 - 已经在
j-1。
对应代码：
a=dp[0][dpi][dpj-1]-abs(ets[j].x-ets[i].x)*(sumv[dpj-1]-sumv[dpi-1]);
b=dp[1][dpi][dpj-1]-abs(ets[j].x-ets[j-1].x)*(sumv[dpj-1]-sumv[dpi-1]);
dp[1][dpi][dpj] = max(a,b)+dp[0][dpj][dpj];
最后所有彩蛋都被处理完，即区间为 [1,n]。由于初始化时没有计算从 x0 出发到第一个彩蛋的时间损失，所以最后需要补上这一段移动产生的损失：
int ans = max(dp[0][1][n]-abs(ets[begin].x-x0)*sumv[n],dp[1][1][n]-abs(ets[end].x-x0)*(sumv[n]));
题目要求输出的是分数，代码中一直把分数放大了 1000 倍来避免小数误差，所以最后除以 1000.0 并保留三位小数。
时间复杂度为 O(n^2)，空间复杂度为 O(n^2)。
易错
- 左边的点接到后面时要写：
ets[i+n]=ets[i];
不能写成 ets[i+n]=ets[begin-i]。后者会把左侧顺序反过来，导致环形序列的区间含义和转移不一致。
- 单点区间初始化后必须
continue：
if(j == i){dp[0][dpi][dpj]=dp[1][dpi][dpj] =ets[i].y;continue;
}
否则会继续执行下面的转移，访问空区间状态，把正确的初始化值覆盖掉。
sumv的下标使用的是压缩后的 DP 下标，不是原始ets下标，所以代码里要用：
sumv[i-base]=sumv[i-base-1]+ets[i].v;
-
最后答案要补上从
x0到最终起点方向的移动损失，否则会少算一段所有彩蛋同时下降的时间。 -
输出要用
printf("%.3f",ansd);，题目要求保留三位小数。
代码
#include<bits/stdc++.h>using namespace std;
#define int long long
#define itn long long
#define tin long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N=2e3+10;
int n,x0;
struct et{int x,y,v;et(int x,int y,int v):x(x),y(y),v(v){};et(){};
};
et ets[N];
int dp[2][N>>1][N>>1];
int sumv[N>>1];
bool cmp(et a,et b){return a.x<b.x;
}
signed main(){IOS;cin>>n>>x0;for(int i=1;i<=n;i++){cin>>ets[i].x;}for(int i=1;i<=n;i++)cin>>ets[i].y;for(int i=1;i<=n;i++)cin>>ets[i].v;int begin = 1;sort(ets+1,ets+1+n,cmp);for(begin;begin<=n;begin++){if(ets[begin].x>=x0)break;}for(int i=1;i<begin;i++)ets[i+n]=ets[i];itn end = begin+n-1;int base=begin-1;for(int i=begin;i<=end;i++){sumv[i-base]=sumv[i-base-1]+ets[i].v;}for(int len =1;len<=n;len++){for(int i=begin;i+len-1<=end;i++){int j=i+len-1;int dpi=i-base,dpj=j-base;if(j == i){dp[0][dpi][dpj]=dp[1][dpi][dpj] =ets[i].y;continue;}int a=dp[0][dpi+1][dpj]-abs(ets[i+1].x-ets[i].x)*(sumv[dpj]-sumv[dpi]);int b=dp[1][dpi+1][dpj]-abs(ets[j].x-ets[i].x)*(sumv[dpj]-sumv[dpi]);dp[0][dpi][dpj] = max(a,b)+dp[0][dpi][dpi];a=dp[0][dpi][dpj-1]-abs(ets[j].x-ets[i].x)*(sumv[dpj-1]-sumv[dpi-1]);b=dp[1][dpi][dpj-1]-abs(ets[j].x-ets[j-1].x)*(sumv[dpj-1]-sumv[dpi-1]);dp[1][dpi][dpj] = max(a,b)+dp[0][dpj][dpj];}}int ans = max(dp[0][1][n]-abs(ets[begin].x-x0)*sumv[n],dp[1][1][n]-abs(ets[end].x-x0)*(sumv[n]));double ansd=ans/(1000.0);printf("%.3f",ansd);return 0;
}