HDU 4719 Oh My Holy FFF(DP+线段树)(2013 ACM/ICPC Asia Regional Online ―― Warmup2)
Description
o o o o o o o o o o o o o o o o o o /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
You, as the captain of *FFF*, want to divide them into smaller groups, but each group should still be continous in the original line. Like this:
o o o | o o o o | o o o o o o | o o o o o /F\ /F\ /F\ | /F\ /F\ /F\ /F\ | /F\ /F\ /F\ /F\ /F\ /F\ | /F\ /F\ /F\ /F\ /F\ / \ / \ / \ | / \ / \ / \ / \ | / \ / \ / \ / \ / \ / \ | / \ / \ / \ / \ / \
In your opinion, the number of soldiers in each group should be no more than L. Meanwhile, you want your division be "holy". Since the soldier may have different heights, you decide that for each group except the first one, its last soldier(which is the rightmost one) should be strictly taller than the previous group's last soldier. That is, if we set bi as the height of the last soldier in group i. Then for i >= 2, there should be b i > b i-1. You give your division a score, which is calculated as , b 0 = 0 and 1 <= k <= M, if there are M groups in total. Note that M can equal to 1. Given the heights of all soldiers, please tell us the best score you can get, or declare the division as impossible.
Input
Output
题目大意:有n个数,划分为多个部分,假设M份,每份不能多于L个。每个数有一个h[i],每份最右边的那个数要大于前一份最右边的那个数。设每份最右边的数为b[i],求最大的sum{b[i]² - b[i - 1]},1≤i≤M,其中b[0] = 0。
思路:朴素DP为,dp[i]表示以i为结尾的最大划分。那么dp[i] = max{dp[j] - h[j] + h[i]²},1≤i-j≤L,h[j]<h[i]。这种会超时,采取线段树优化。因为有两个限制,考虑到若h[j]≥h[i],那么求i的时候一定不会用到j,那么先按h排序再DP(h相同的,i大的排前面)。
PS:又忘了把int改成long long >_<
代码(781MS):
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL; const int MAXN = ; LL dp[MAXN];
int n, L;
LL tree[MAXN << ], maxt[MAXN << ]; void pushdown(int x) {
int ll = x << , rr = ll ^ ;
if(tree[x] != -) {
tree[ll] = max(tree[x], tree[ll]);
tree[rr] = max(tree[x], tree[rr]);
maxt[ll] = max(maxt[ll], tree[x]);
maxt[rr] = max(maxt[rr], tree[x]);
tree[x] = -;
}
} void update(int x, int left, int right, int a, int b, LL val) {
if(a <= left && right <= b) {
tree[x] = max(tree[x], val);
maxt[x] = max(maxt[x], val);
}
else {
pushdown(x);
int ll = x << , rr = ll ^ ;
int mid = (left + right) >> ;
if(a <= mid) update(ll, left, mid, a, b, val);
if(mid < b) update(rr, mid + , right, a, b, val);
maxt[x] = max(maxt[x], max(maxt[ll], maxt[rr]));
}
} LL query(int x, int left, int right, int a, int b) {
if(a <= left && right <= b) return maxt[x];
else {
pushdown(x);
int ll = x << , rr = ll ^ ;
int mid = (left + right) >> ;
LL ret = -;
if(a <= mid) ret = max(ret, query(ll, left, mid, a, b));
if(mid < b) ret = max(ret, query(rr, mid + , right, a, b));
return ret;
}
} struct Node {
int h, pos;
void read(int i) {
pos = i;
scanf("%d", &h);
}
bool operator < (const Node &rhs) const {
if(h != rhs.h) return h < rhs.h;
return pos > rhs.pos;
}
} a[MAXN]; LL solve() {
sort(a + , a + n + );
dp[n] = -;
memset(tree, , sizeof(tree));
memset(maxt, , sizeof(maxt));
update(, , n, , , );
for(int i = ; i <= n; ++i) {
LL tmp = query(, , n, max(, a[i].pos - L), a[i].pos - );
if(tmp == -) {
if(a[i].pos == n) break;
else continue;
}
dp[a[i].pos] = tmp + LL(a[i].h) * a[i].h;
if(a[i].pos == n) break;
update(, , n, a[i].pos, a[i].pos, dp[a[i].pos] - a[i].h);
}
//for(int i = 1; i <= n; ++i) printf("%I64d\n", dp[i]);
return dp[n];
} int main() {
int T; scanf("%d", &T);
for(int t = ; t <= T; ++t) {
scanf("%d%d", &n, &L);
for(int i = ; i <= n; ++i) a[i].read(i);
LL ans = solve();
if(ans == -) printf("Case #%d: No solution\n", t);
else printf("Case #%d: %I64d\n", t, ans);
}
}
最新文章
- C#之设计模式
- 再谈 $* 和 $@ 在 Bash 中的表现
- sql经常会遇到“将截断二进制或字符串”的错误——处理办法
- ArrayList、Vector、HashMap、HashTable、HashSet的默认初始容量、加载因子、扩容增量
- 动手学习TCP:客户端状态变迁
- 对List里的对象元素进行排序
- 记录C++学习历程
- spring mvc中的valid
- python的资料
- 【技术贴】关闭CMD错误提示声音
- 无法更新 EntitySet“GuigeInfo”,因为它有一个 DefiningQuery,而 <;ModificationFunctionMapping>; 元素中没有支持当前操作的 <;InsertFunction>; 元素。
- threejs 组成的3d管道,寻最短路径问题
- JUnit4测试出错(一)
- reserve的使用
- thymeleaf标签必须由匹配的结束标记终止
- 算法之Python实现 - 002 : 换钱的最少货币数补充(每种货币只能使用一次)
- Oracle 序列(sequence)
- 使用Java泛型返回动态类型
- c++动态库封装及调用(3、windows下动态库调用)
- Uboot USB模式(RK3288变砖头的解决办法)