洛谷 P1721 国王饮水记 —— 斜率dp + 性质 + 高精度

本文主要是介绍洛谷 P1721 国王饮水记 —— 斜率dp + 性质 + 高精度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 个城市，每个城市有高为 $h_i$ 的水
    使用一次地下连通系统，可以任意指定城市，水位然后保持一致
    要求最多使用 $k$ 次地下连通系统，使得 $1$ 号城市水位最高
    保留 $p$ 位小数

解题思路：

    这里只写个大概，详细题解请见这里

    忽略比 $h_1$ 小的数，然后按照 $h$ 排序
    易得合并两个比合并三个更优，那么只考虑 $k<n$ 的情况
    在易得肯定是一段一段的合并最优，就可以 $dp$ 转移了
    $dp[i][j]$ 前 $i$ 个合并 $j$ 次的最优值，$s_i$ 为前缀
    $dp[i][j]=max(dp[k][j-1]+s_i-s_k)/(i-k+1)$
    转换一下就 $=(s_i-(s_k-dp[k][j-1]))/(i-(k-1))$
    每个状态看成点 $(k-1,s_k-dp[k][j-1])$，使得斜率最大，维护下凸包
    易得具有决策单调性，时间复杂度：$O(nkp)$

    其实发现用 $double$ 的精度就可以计算出答案了
    因此 $p$ 的复杂度可以最后拿出来，时间复杂度：$O(nk)$

    然而这样在 $bzoj$ 上是被卡内存的
    观察会发现更多奇奇怪怪的性质
    所有 $h_i$ 互不相等 —— 每次转移的区间长度不会大于上一次转移的区间长度
    长度大于 $1$ 的区间个数不会超过 $O(log\frac{nh}{\Delta })$，其中 $\Delta =min(h_i-h_{i-1})$
    最后我们只需要 $dp$ 大概 $14$ 层即可
    时间复杂度：$O(14n+kp)$，( 这份代码没用高精度类 )

    所有性质及证明参考这里

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 8005;
int n, k, p, h[maxn], tot;
int zy[maxn][20], s[maxn], q[maxn];
double dp[maxn][20], ans;
int a[3005];
struct node{double x, y;
} nd[maxn];double slope(node a, node b){return (a.y - b.y) / (a.x - b.x);
}
void div(int x){ll tmp = 0;for(int i=0; i<=p; i++){tmp = tmp * 1000000000 + a[i];a[i] = tmp / x; tmp %= x;}
}
double cal(int i, int j){if(!j) return h[1];return (cal(zy[i][j], j-1) + s[i] - s[zy[i][j]]) / (i - zy[i][j] + 1);
}
void cala(int i, int j){	//	递归计算 if(!j) {a[0] += h[1];return;}cala(zy[i][j], j-1);a[0] += s[i] - s[zy[i][j]];div(i - zy[i][j] + 1);
}signed main() {scanf("%d%d%d%d", &n, &k, &p, &h[tot=1]); p = p / 9 + 1;	//	注意输出限制 for(int i=2; i<=n; i++) {scanf("%d", h+i);if(h[i] > h[1]) h[++tot] = h[i];}n = tot; sort(h+1, h+1+n); k = min(k, n);for(int i=1; i<=n; i++) s[i] = s[i-1] + h[i], dp[i][0] = h[1];int lim = min(14, k);for(int j=1; j<=lim; j++){int head = 1, tail = 0; q[++tail] = 1;for(int i=1; i<=n; i++) nd[i] = {i - 1, s[i] - dp[i][j-1]};for(int i=2; i<=n; i++){node u = {i, s[i]};while(head<tail && slope(u, nd[q[head]])<slope(u, nd[q[head+1]])) head++;zy[i][j] = q[head], dp[i][j] = slope(u, nd[q[head]]);while(head<tail && slope(nd[q[tail-1]], nd[q[tail]])>slope(nd[q[tail]], nd[i])) tail--;q[++tail] = i;}}int m = n - k + lim, pos; double mx = 0;for(int j=0; j<=lim; j++) if(mx <= dp[m][j]) mx = dp[m][j], pos = j;
//	ans = cal(m, pos);
//	for(int i=m+1; i<=n; i++) ans = (ans + h[i]) / 2;
//	cout << ans << endl;cala(m, pos);for(int i=m+1; i<=n; i++) a[0] += h[i], div(2);printf("%d.", a[0]);for(int i=1; i<=p; i++) printf("%09d", a[i]);
}

这篇关于洛谷 P1721 国王饮水记 —— 斜率dp + 性质 + 高精度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---