[dp]答疑
题目描述
在一个数轴上，有 n n n 个同学等待老师的答疑。老师最先站在 k k k 号同学的位置。老师需要解决所有同学的问题，解决一个问题都只需要 0 0 0 秒。学生很没有耐心，每等一秒钟就会增加 w i w_i wi 的不开心值。老师以 1 m / s 1m/s 1m/s 的速度开始行动，他想知道解决完所有同学的问题最少需要多少的不开心值。
输入格式
第一行输入两个整数
n
n
n 和
k
k
k，表示等待答疑的学生数量和老师最先站在几号同学的旁边。
接下来
n
n
n 行，每行两个整数
x
x
x 和
y
y
y，表示第
i
i
i 个同学的位置和每秒增加的不开心值。
输出格式
输出一行一个整数表示最小的不开心值。
数据范围
对于
40
%
40\%
40% 的数据，
2
≤
n
≤
7
2 \le n \le 7
2≤n≤7。
对于
100
%
100\%
100% 的数据，
2
≤
n
≤
1000
2 \le n \le 1000
2≤n≤1000，
1
≤
k
≤
1000
1 \le k \le 1000
1≤k≤1000
0
≤
x
,
y
≤
1000
0 \le x,y \le 1000
0≤x,y≤1000。
样例
样例输入1
4 3
2 2
5 8
6 1
8 7
样例输出1
56
题解
1
对于 40 % 40\% 40% 的数据，我们可以直接暴力枚举，枚举到每个学生的顺序，计算出不开心值。
进而，我们可以将枚举进化，可以得到
60
60
60 分。
我们还是 dfs 出每个位置，边枚举边计算不开心值，进行剪枝。
在 dfs 前，可以先排序，在实践中发现排序后一般比不排序快
x 表示解决的数量，z 表示现在的不开心值（即每秒增加的不开心），s 表示不开心值，o 记录上一次走到的位置
inline void dfs(int x, int z, int s, int o){
//剪枝
if(s >= ans){
return;
}
if(x > n){
ans = min(ans, s);
return;
}
for(int i = o - 1; i >= 1; -- i){
if(!f[i]){
f[i] = 1;
dfs(x + 1, z - u[i].b, s + abs(u[o].a - u[i].a) * z, i);
f[i] = 0;
}
}
for(int i = o + 1; i <= n; ++ i){
if(!f[i]){
f[i] = 1;
dfs(x + 1, z - u[i].b, s + abs(u[o].a - u[i].a) * z, i);
f[i] = 0;
}
}
}
这里 dfs 也可以优化到
100
100
100 分，跟下面做法类似。
2
考虑使用 区间dp，记录从
i
i
i 到
j
j
j 的最小不开心值（
i
≤
j
i \le j
i≤j）。
从 i i i 到 j j j 的区间，有两种情况：
- 从 i i i 开始到 j j j，到 j j j 停止。
- 从 j j j 开始到 i i i，到 i i i 停止。
定义
f
i
,
j
,
0
/
1
f_{i,j,0/1}
fi,j,0/1 表示从
i
i
i 到
j
j
j 和从
j
j
j 到
i
i
i 的最小不开心值。
最开始
f
k
,
k
,
0
f_{k,k,0}
fk,k,0 和
f
k
,
k
,
1
f_{k,k,1}
fk,k,1 都为
0
0
0（因为老师最开始就在
k
k
k 同学位置），其他位置都为无穷大。
考虑转移 f i , j , 0 f_{i,j,0} fi,j,0，它可以从 f i , j − 1 , 0 f_{i,j-1,0} fi,j−1,0 转移过来，即从 i i i 到 j j j，可以先从 i i i 到 j − 1 j - 1 j−1，再从 j − 1 j - 1 j−1 到 j j j；也可以从 f i , j − 1 , 1 f_{i,j-1,1} fi,j−1,1 转移过来，即从 j − 1 j - 1 j−1 到 i i i，再从 i i i 到 j j j。尽管第二个方法看起来不是很优，但不开心值也可能比第一种小。
接下来就是计算 w w w 了。可以用一个前缀和数组 s u m sum sum 记录从 w 1 w_1 w1 到 w i w_i wi 的和。这下从 i i i 到 j j j 的区间，不开心值就是排除 i i i 到 j j j 的区间和，这里 j j j 是将要到的，并没有到，所以不计 j j j 的不开心值。
因此，我们就可以得出
f
i
,
j
,
0
f_{i,j,0}
fi,j,0 的转移。
f
i
,
j
,
0
=
min
(
f
i
,
j
,
0
,
f
i
+
1
,
j
,
0
+
(
∣
x
j
+
1
.
a
−
x
j
.
a
∣
)
×
(
s
u
m
n
−
s
u
m
k
+
s
u
m
j
)
,
f
j
+
1
,
k
,
1
+
(
∣
x
k
.
a
−
x
j
.
a
∣
)
×
(
s
u
m
n
−
s
u
m
k
+
s
u
m
j
)
)
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))
同理，我们可以的出 f i , j , 1 f_{i,j,1} fi,j,1 的转移。
答案就是 min ( f 1 , n , 0 , f 1 , n , 1 ) \min(f_{1,n,0}, f_{1,n,1}) min(f1,n,0,f1,n,1) 的值。
//前缀和
for(int i = 1; i <= n; ++ i){
sum[i] = sum[i - 1] + x[i].b;
}
//预处理 dp 数组
for(int i = 0; i <= n + 1; ++ i){
for(int j = 0; j <= n + 1; ++ j){
f[i][j][0] = f[i][j][1] = 1e16;
}
}
f[m][m][0] = f[m][m][1] = 0;
//转移
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= n - i; ++ j){
//这里的 j 就是上文的 i, k 就是上文的 j
int k = i + j;
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])));
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])));
}
}
禁止抄袭!!!