[dp]答疑

标题形貌

在一个数轴上，有 nnn 个同砚等候老师的答疑。老师开始站在 kkk 号同砚的位置。老师必要办理全部同砚的题目，办理一个题目都只必要 000 秒。弟子很没有耐烦，每等一秒钟就会增长 wiw_iwi​ 的不开心值。老师以 1m/s1m/s1m/s 的速率开始办法，他想知道办理完全部同砚的题目最少必要多少的不开心值。
输入格式

第一行输入两个整数 nnn 和 kkk，体现等候答疑的弟子数目和老师开始站在几号同砚的旁边。
接下来 nnn 行，每行两个整数 xxx 和 yyy，体现第 iii 个同砚的位置和每秒增长的不开心值。
输特别式

输出一行一个整数体现最小的不开心值。
数据范围

对于 40%40\%40% 的数据，2≤n≤72 \le n \le 72≤n≤7。
对于 100%100\%100% 的数据，2≤n≤10002 \le n \le 10002≤n≤1000，1≤k≤10001 \le k \le 10001≤k≤10000≤x,y≤10000 \le x,y \le 10000≤x,y≤1000。
样例

样例输入1

1. 4 3
2. 2 2
3. 5 8
4. 6 1
5. 8 7

复制代码

样例输出1

1. 56

复制代码

题解

1

对于 40%40\%40% 的数据，我们可以直接暴力罗列，罗列到每个弟子的序次，盘算出不开心值。
进而，我们可以将罗列进化，可以得到 606060 分。
我们还是 dfs 出每个位置，边罗列边盘算不开心值，举行剪枝。

1. 在 dfs 前，可以先排序，在实践中发现排序后一般比不排序快
2. x 表示解决的数量，z 表示现在的不开心值（即每秒增加的不开心），s 表示不开心值，o 记录上一次走到的位置
3. inline void dfs(int x, int z, int s, int o){
4.         //剪枝
5.         if(s >= ans){
6.                 return;
7.         }
8.         if(x > n){
9.                 ans = min(ans, s);
10.                 return;
11.         }
12.         for(int i = o - 1; i >= 1; -- i){
13.                 if(!f[i]){
14.                         f[i] = 1;
15.                         dfs(x + 1, z - u[i].b, s + abs(u[o].a - u[i].a) * z, i);
16.                         f[i] = 0;
17.                 }
18.         }
19.         for(int i = o + 1; i <= n; ++ i){
20.                 if(!f[i]){
21.                         f[i] = 1;
22.                         dfs(x + 1, z - u[i].b, s + abs(u[o].a - u[i].a) * z, i);
23.                         f[i] = 0;
24.                 }
25.         }
26. }

复制代码

这里 dfs 也可以优化到 100100100 分，跟下面做法类似。
2

思量利用 区间dp，记载从 iii 到 jjj 的最小不开心值（i≤ji \le ji≤j）。
从 iii 到 jjj 的区间，有两种环境：

• 从 iii 开始到 jjj，到 jjj 克制。
  
• 从 jjj 开始到 iii，到 iii 克制。
  

界说 fi,j,0/1f_{i,j,0/1}fi,j,0/1​ 体现从 iii 到 jjj 和从 jjj 到 iii 的最小不开心值。
最开始 fk,k,0f_{k,k,0}fk,k,0​ 和 fk,k,1f_{k,k,1}fk,k,1​ 都为 000（由于老师最开始就在 kkk 同砚位置），其他位置都为无穷大。
思量转移 fi,j,0f_{i,j,0}fi,j,0​，它可以从 fi,j−1,0f_{i,j-1,0}fi,j−1,0​ 转移过来，即从 iii 到 jjj，可以先从 iii 到 j−1j - 1j−1，再从 j−1j - 1j−1 到 jjj；也可以从 fi,j−1,1f_{i,j-1,1}fi,j−1,1​ 转移过来，即从 j−1j - 1j−1 到 iii，再从 iii 到 jjj。只管第二个方法看起来不是很优，但不开心值也大概比第一种小。
接下来就是盘算 www 了。可以用一个前缀和数组 sumsumsum 记载从 w1w_1w1​ 到 wiw_iwi​ 的和。这下从 iii 到 jjj 的区间，不开心值就是扫除 iii 到 jjj 的区间和，这里 jjj 是将要到的，并没有到，以是不计 jjj 的不开心值。
因此，我们就可以得出 fi,j,0f_{i,j,0}fi,j,0​ 的转移。
fi,j,0=min⁡(fi,j,0,fi+1,j,0+(∣xj+1.a−xj.a∣)×(sumn−sumk+sumj),fj+1,k,1+(∣xk.a−xj.a∣)×(sumn−sumk+sumj))f_{i,j,0} = \min(f_{i,j,0},  f_{i + 1, j, 0} + (\mid x_{j + 1}.a - x_{j}.a\mid) \times (sum_n - sum_k + sum_j),  f_{j + 1, k, 1} + (\mid x_{k}.a - x_{j}.a \mid) \times (sum_{n} - sum_{k} + sum_{j}))fi,j,0​=min(fi,j,0​,fi+1,j,0​+(∣xj+1​.a−xj​.a∣)×(sumn​−sumk​+sumj​),fj+1,k,1​+(∣xk​.a−xj​.a∣)×(sumn​−sumk​+sumj​))
同理，我们可以的出 fi,j,1f_{i,j,1}fi,j,1​ 的转移。
答案就是 min⁡(f1,n,0,f1,n,1)\min(f_{1,n,0}, f_{1,n,1})min(f1,n,0​,f1,n,1​) 的值。

1. //前缀和
2. for(int i = 1; i <= n; ++ i){
3.         sum[i] = sum[i - 1] + x[i].b;
4. }
5. //预处理 dp 数组
6. for(int i = 0; i <= n + 1; ++ i){
7.         for(int j = 0; j <= n + 1; ++ j){
8.                 f[i][j][0] = f[i][j][1] = 1e16;
9.         }
10. }
11. f[m][m][0] = f[m][m][1] = 0;
13. //转移
14. for(int i = 1; i <= n; ++ i){
15.         for(int j = 1; j <= n - i; ++ j){
16.                 //这里的 j 就是上文的 i, k 就是上文的 j
17.                 int k = i + j;
18.                 f[j][k][0] = min(f[j][k][0], min(f[j + 1][k][0] + abs(x[j + 1].a - x[j].a) * (sum[n] - sum[k] + sum[j]), f[j + 1][k][1] + abs(x[k].a - x[j].a) * (sum[n] - sum[k] + sum[j])));
19.                 f[j][k][1] = min(f[j][k][1], min(f[j][k - 1][1] + abs(x[k].a - x[k - 1].a) * (sum[n] - sum[k - 1] + sum[j - 1]), f[j][k - 1][0] + abs(x[k].a - x[j].a) * (sum[n] - sum[k - 1] + sum[j - 1])));
20.         }
21. }

复制代码

克制抄袭!!!