【noip模拟】修长城

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);

 }

挫挫滴代码

秒客网