hdu 4719 Oh My Holy FFF(线段数+dp)

2024-06-05 03:32

文章标签 dp hdu 线段 fff oh holy 4719

本文主要是介绍hdu 4719 Oh My Holy FFF(线段数+dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接:hdu 4719 Oh My Holy FFF

题目大意：队伍里有n个人，给出每个人的身高，他们按照顺序排列，现在要将这n个人分成若干组，每一组的人数不得大于l，并且第i组的最后一个人的身高一定要大于第i−1组的最后一个人的身高。要求最后的权值最大，权值计算方法在题目中,k为组号。

解题思路：dp[i]表示以第i个人作为结尾的最大权值，那么dp[i]肯定是从前面的l-1个中转移过来的，即dp[i]=dp[j]+h[i]2−h[j] 要求h[i]>h[j].
但是这样的复杂度为o(n2),然后n最大为105,时间上不能接受，所以用线段树代替查询操作，但是转移的条件有说h[i]>h[j],所以我们要先将每个人按照身高排序，这样就逐个计算就不需要考虑身高的限制，因为如果已经被更新了的值，身高肯定小于当前需要考虑的人。
并且将要查找的值b[i]=dp[i]−h[j].
线段树没正式接触过，所以写的非常搓，也没有延时更新。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;
typedef long long ll;
const int N = 1e5+5;struct state {int pos;ll high;
}p[N];struct node {int left;int right;ll val;
}t[N*4];int n, k;
ll dp[N];inline ll max(ll a, ll b) {return a > b ? a : b;
}ll BuildTree (int c, int l, int r) {t[c].left = l;t[c].right = r;if (l == r) {t[c].val = -1;} else {int mid = (l + r)/2;t[c].val = max(BuildTree(c*2, l, mid), BuildTree(c*2+1, mid+1, r));}return t[c].val;
}ll Query (int c, int l, int r) {if (l == t[c].left && r == t[c].right)return t[c].val;int mid = (t[c].left + t[c].right) / 2;if (l <= mid && r > mid)return max(Query(c*2, l, mid), Query(c*2+1, mid+1, r));else if (l <= mid && r <= mid)return Query(c*2, l, r);elsereturn Query(c*2+1, l, r);
}ll upDate (int c, int l, int r, ll val) {if (l == t[c].left && r == t[c].right) {t[c].val = val;return val;}int mid = (t[c].left + t[c].right) / 2;if (l <= mid && r > mid)return t[c].val = max(upDate(c*2, l, mid, val), upDate(c*2+1, mid+1, r, val));else if (l <= mid && r <= mid)return t[c].val = max(upDate(c*2, l, r, val), t[c*2+1].val);elsereturn t[c].val = max(t[c*2].val, upDate(c*2+1, l, r, val));
}inline bool cmp (const state& a, const state& b) {if (a.high != b.high)return a.high < b.high;return a.pos > b.pos;
}void init () {scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++) {cin >> p[i].high;p[i].pos = i;}sort(p+1, p+n+1, cmp);BuildTree(1, 0, n);
}ll solve () {upDate(1, 0, 0, 0);for (int i = 1; i <= n; i++) {dp[p[i].pos] = -1;ll val = Query(1, max(0, p[i].pos-k), p[i].pos-1);//cout << val << " " << p[i].pos << endl;if (val == -1) continue;dp[p[i].pos] = val + p[i].high * p[i].high;if (p[i].pos == n)break;upDate(1, p[i].pos, p[i].pos, dp[p[i].pos] - p[i].high);}return dp[n];
}int main () {int cas;scanf("%d", &cas);for (int i = 1; i <= cas; i++) {init ();cout << "Case #" << i << ": ";ll ans = solve();if (ans <= 0)cout << "No solution" << endl;elsecout << ans << endl;}return 0;
}