本文主要是介绍[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 就是上文的 jint 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])));}
}
禁止抄袭!!!
这篇关于[dp]答疑的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
