HDU4719-Oh My Holy FFF(DP線段樹優化)
Oh My Holy FFF
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 606 Accepted Submission(s): 141
Problem Description
N soldiers from the famous "*FFF* army" is standing in a line, from left to right.
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, Z喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vciBkZWNsYXJlIHRoZSBkaXZpc2lvbiBhcyBpbXBvc3NpYmxlLgoKIAo8YnI+CgpJbnB1dAoKVGhlIGZpcnN0IGxpbmUgaGFzIGEgbnVtYmVyIFQgKFQgPD0gMTApICwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuPGJyPgpGb3IgZWFjaCB0ZXN0IGNhc2UsIGZpcnN0IGxpbmUgaGFzIHR3byBudW1iZXJzIE4gYW5kIEwgKDEgPD0gTCA8PSBOIDw9IDEwPHN1cD41PC9zdXA+KSwgYXMgZGVzY3JpYmVkIGFib3ZlLjxicj4KVGhlbiBjb21lcyBhIHNpbmdsZSBsaW5lIHdpdGggTiBudW1iZXJzLCBmcm9tIEgxIHRvIEhuLCB0aGV5IGFyZSB0aGUgaGVpZ2h0IG9mIGVhY2ggc29sZGllciBpbiB0aGUgbGluZSwgZnJvbSBsZWZ0IHRvIHJpZ2h0LiAoMSA8PSBIPHN1Yj5pPC9zdWI+IDw9IDEwPHN1cD41PC9zdXA+KQoKIAo8YnI+CgpPdXRwdXQKCkZvciB0ZXN0IGNhc2UgWCwgb3V0cHV0IA=="Case #X: " first, then output the best score.
Sample Input
2
5 2
1 4 3 2 5
5 2
5 4 3 2 1
Sample Output
Case #1: 31
Case #2: No solution
題意：
n(n < 1e5)個人排成一行，把它切成若干堆，要求每一堆的長度不超過l(l < 1e5),並且每一堆的最右一個人的身高都要比前一堆的最右一個人的身高要高，對於每一種方案，它的分數是SUM(b[k]^2-b[k-1] ) b[k] 為第k堆最右一個人的身高 要求最高的分數。
思路：
樸素的DP 是 DP[i] = max(DP[j] - b[j]) + b[i]*b[i] ( i-l <= j <= i-1 ) 但是這樣會超時（O(n^2)） 可以發現每次求DP[i] 的時候 實際就是求 區間[i-l,i-1] DP[j]-b[j]的最大值，因此可以利用線段樹優化，此時還需要解決一個問題：就是如何保證每次求DP[i]的時候保證區間[i-l,i-1]
的每個人的身高都是比自己矮的？ 可以進行先排序，讓矮的人先選，如果身高一樣就讓序號在後的先選，這樣就不會有沖突了（單點更新的時候）。 每次查詢的時候單點更新即可。
#include
#include
#include
#include
#include
using namespace std;
#define REP(_,a,b) for(int _=(a); _<=(b);++_)
#define sz(s) (int)((s).size())
typedef long long ll;
const int maxn = 1e5+10;
int n,l;
ll dp[maxn];
struct Num{
ll h;
int idx;
Num(ll h = 0,int idx = 0):h(h),idx(idx){}
friend bool operator < (Num a,Num b){
if(a.h!=b.h) return a.h < b.h;
else return a.idx > b.idx;
}
};
vector vN;
struct node{
int lson,rson;
ll maxx;
int mid(){
return (lson+rson)>>1;
}
}tree[maxn*4];
void pushUp(int rt){
tree[rt].maxx = max(tree[rt<<1].maxx,tree[rt<<1|1].maxx);
}
void build(int L,int R,int rt){
tree[rt].lson = L;
tree[rt].rson = R;
tree[rt].maxx = -1;
if(L==R){
return;
}
int mid = tree[rt].mid();
build(L,mid,rt<<1);
build(mid+1,R,rt<<1|1);
}
void init(){
vN.clear();
memset(dp,-1,sizeof dp);
}
void update(int pos,int l,int r,int rt,ll x){
if(l==r){
tree[rt].maxx = x;
return;
}
int mid = tree[rt].mid();
if(pos<=mid){
update(pos,l,mid,rt<<1,x);
}else{
update(pos,mid+1,r,rt<<1|1,x);
}
pushUp(rt);
}
ll query(int L,int R,int l,int r,int rt){
if(L <=l && R >= r){
return tree[rt].maxx;
}
int mid = tree[rt].mid();
ll ret;
bool flag = false;
if(L <= mid){
ret = query(L,R,l,mid,rt<<1);
flag = true;
}
if(R > mid){
if(flag){
ret = max(ret,query(L,R,mid+1,r,rt<<1|1));
}else{
ret = query(L,R,mid+1,r,rt<<1|1);
}
}
return ret;
}
void input(){
scanf("%d%d",&n,&l);
for(int i = 1; i <= n; i++){
ll h;
scanf("%I64d",&h);
vN.push_back(Num(h,i));
}
sort(vN.begin(),vN.end());
build(0,n,1);
}
void solve(){
update(0,0,n,1,0);
REP(_,0,sz(vN)-1) {
int ni = vN[_].idx;
ll nh = vN[_].h;
ll tm = query(max(ni-l,0),ni-1,0,n,1);
if(tm>=0){
dp[ni] = tm+nh*nh;
update(ni,0,n,1,dp[ni]-nh);
}
if(ni==n) break;
}
if(dp[n]<=0){
printf("No solution\n");
}else{
printf("%I64d\n",dp[n]);
}
}
int main(){
int ncase,T=1;
cin >> ncase;
while(ncase--){
init();
input();
printf("Case #%d: ",T++);
solve();
}
return 0;
}
