Time Limit: 1000ms Memory Limit: 256MB
Description
大家都知道，长城在自然条件下会被侵蚀，因此，我们需要修复。现在是21世纪，修复长城的事情当然就交给机器人来干辣。我们知道，长城每时每刻都在受到侵蚀，如果现在不修复，以后修复的代价会更高。现在，请你写一个程序来确定机器人修长城的顺序，使得修复长城的代价最小。
在这道题中，我们认为长城是一条很长的线段，长城的每个位置都有唯一的数字与它对应（即当前位置到长城某一端的距离）。这台机器人开始被放在一个给定的初始位置，并以一个恒定的速率行驶。对于每个损坏的地方，你都知道它具体的位置、现在修复的代价、以后修复代价会怎么增加。由于机器人效率特别高，机器人每到损坏的地方就能瞬间将该位置修复。
Input
第一行三个整数 $n,v,x(1≤n≤1000,1≤v≤100,1≤x≤500000)$ ，分别表示长城损坏地方的数目、机器人在1个单位时间内移动的长度、机器人的初始位置。
接下来n行，每行三个整数 $x,c,u(1≤x≤500000,0≤c≤50000,1≤u≤50000)$ 。x代表损坏地方的位置。如果立即修复，则该损坏位置修复的代价为c。如果选择在t时刻后修复，则该损坏位置修复的代价为c+u*t。数据保证所有损坏的位置都是不同的，机器人刚开始不会站在损坏的位置上面。
Output
输出只有一个整数，修复整个长城的最小代价（如果是小数，则向下取整）。
对于下面第一组样例的解释：
首先去998位置修复，费用为600。
然后去1010位置修复，费用为1400。
最后去996位置修复，费用为84。
最终答案为2084。
Sample Input
【样例输入1】
3 1 1000
1010 0 100
998 0 300
996 0 3
【样例输入2】
3 1 1000
1010 0 100
998 0 3
996 0 3
Sample Output
【样例输出1】
2084
【样例输出2】
1138
HINT
对于10%的数据，$ n≤10$
对于20%的数据， $n≤20$
对于50%的数据， $n≤100$
对于100%的数据，$n≤1000$
[吐槽]
最近各种脑抽。。于是乎仿佛是完全不会dp了qwq
[题解]
显然那个维修的初始值是一点用都没有的最后再加上就好了
然后只用看其他的东西
首先有一个比较重要的性质
修补过的肯定是一个连续的区间
那么考虑一个$n^2$的dp
$f_{i,j}$表示已经修完了$x_i$到$x_j$这段区间，并且停在$x_i$的时候，要修补完剩下区间的最小花费
$g_{i,j}$表示（同上），并且停在$x_j$的时候，要修完剩下区间的最小花费
这样就可以直接加了呀每次就加上这段移动需要的花费，式子就很好推了
那么再引入两个定义
$s1_i$表示的是花费的前缀和
$s2_i$表示的是花费的后缀和
那么就有
$f_{i,j}=min(f_{i-1,j}+(x_{i+1}-x_{i})*(s1_{i}+s2_{j+1}),g_{i+1,j}+(x_{j}-x_{i})*(s1_{i}+s2_{j+1}))$
$g_{i,j}=min(g_{i,j-1}+(x_{j}-x_{j-1})*(s1_{i-1}+s2_{j}),f_{i,j-1}+(x_{j}-x_{i})*(s1_{i-1}+s2_{j]})$
同时还有从$g$走到$f$和从$f$走到$g$的，也就是
$f_{i,j}=min(f_{i,j},g_{i,j}+(x_j-x_i)*(s1_{i-1}+s2_{j+1}))$
$g_{i,j}=min(g_{i,j},f_{i,j}+(x_j-x_i)*(s1_{i-1}+s2_{j+1}))$
相互影响？
仔细想一下就会发现如果相互影响的话就不会用来更新了
所以没有关系
然后就很玄妙滴搞完啦ovo
[一些细节]
long long 没啦qwq
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Min(x,y) x<y?x:y
#define ll long long
using namespace std;
const int MAXN=;
struct data
{
int x,w,c;
}a[MAXN];
ll f[MAXN][MAXN],g[MAXN][MAXN];
ll s1[MAXN],s2[MAXN];
int n,m,st;
ll ans;
bool cmp(data x,data y) {return x.x<y.x;}
int abs1(int x) {return x>?x:-x;} int main()
{
// freopen("a.in","r",stdin); scanf("%d%d%d",&n,&m,&a[].x);
for (int i=;i<=n;++i)
scanf("%d%d%d",&a[i].x,&a[i].c,&a[i].w),ans+=a[i].c;
sort(a+,a++n,cmp);
for (int i=;i<=n;++i) s1[i]=s1[i-]+a[i].w;
for (int i=n;i>=;--i) s2[i]=s2[i+]+a[i].w;
memset(f,0x7f,sizeof(f));
for (int i=;i<=n;++i) f[i][i]=g[i][i]=abs1(a[i].x-a[].x)*s1[n];
for (int i=n;i>=;--i)
for (int j=i+;j<=n;++j)
{
f[i][j]=Min(f[i+][j]+(a[i+].x-a[i].x)*(s1[i]+s2[j+]),g[i+][j]+(a[j].x-a[i].x)*(s1[i]+s2[j+]));
g[i][j]=Min(g[i][j-]+(a[j].x-a[j-].x)*(s1[i-]+s2[j]),f[i][j-]+(a[j].x-a[i].x)*(s1[i-]+s2[j]));
f[i][j]=Min(f[i][j],g[i][j]+(a[j].x-a[i].x)*(s1[i-]+s2[j+]));
g[i][j]=Min(g[i][j],f[i][j]+(a[j].x-a[i].x)*(s1[i-]+s2[j+]));
}
ans+=(ll)f[][n]/m;
printf("%lld\n",ans);
}
挫挫滴代码