首页 > 代码库 > HDU 4719 数据结构

HDU 4719 数据结构

2024-07-03 16:51:49   225人阅读

给出一个序列，将其分割成长度不超过L的若干组。（设为M组）

设B0=0,取出第i组的最后一个数设为Bi

若B序列单调递增，则该划分合法。

在这个前提下，使得 分数= sigma（Bi^2-Bi-1）最大  (i>0);

 

设元素为a[i];

其实就是求一个上升子序列，且元素之间的差不超过L，

在求的过程中维护当前的分数即可。

设F[i]为以第i个数结尾的上升子序列的分数-a[i];

这样的话转移方程很明显 F[i] = max(F[i-L]..F[i-1])+a[i]*a[i]-a[i];

ANS = F[N]+a[N]

为了保证序列单调上升，我们按照元素从小到大的顺序填F数组，未填的元素为-1

为保证严格上升，若元素相等，先填后面的元素（见cmp函数）

 

维护区间最大值，用树状数组即可。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;
const ll INF = 1ll<<62;
const int MAXN = 100010;
ll Tree[MAXN];
ll save[MAXN];
int a[MAXN];
int Index[MAXN];
int N,L;
int _;

inline int lowbit(int p){
    return p&-p;
}

void update(int p){
    for (int i=p;i<=N;i+=lowbit(i))
        Tree[i] = max(Tree[i],save[p]);
}

ll findmax(int l,int r){
    r--;
    l--;
    ll mm = -1;
    while(r!=l){
        int ll = r-lowbit(r);
        if (ll<l){
            mm = max(mm,save[r]);
            r--;
        } else {
            mm = max(mm,Tree[r]);
            r = ll;
        }
    }
    return mm;
}

bool cmp(int i,int j){
    if (a[i]==a[j]) return i>j;
    return a[i]<a[j];
}

int main(){
    freopen("in.txt","r",stdin);
    scanf("%d",&_);
    int cas=0;
    while(_--){
        scanf("%d%d",&N,&L);
        for (int i=1;i<=N;i++) scanf("%d",&a[i]);
        memset(Tree,-1,sizeof(Tree));
        memset(save,-1,sizeof(save));
        for (int i=1;i<=N;i++) Index[i] = i;
        sort(Index+1,Index+N+1,cmp);
        for (int i=1;i<=N;i++){
            int np = Index[i];
            if (np<=L) save[np] = 1ll*a[np]*a[np]-a[np];
            ll M = findmax(max(np-L,1),np);
            if (M!=-1) save[np] = max(save[np],M+1ll*a[np]*a[np]-a[np]);
            update(np);
        }
        cout << "Case #" << ++cas << ": ";
        if(save[N]==-1) cout << "No solution" << endl; else cout << save[N]+a[N] << endl;
    }
}
View Code

 


联系
我们