【bzoj3897】Power

2015.03.26 07:03 Thu | 20次阅读 | 旧日oi | 固定链接 | 源码

Description

我们假设小T有一个人体耐力上限E,在月初的时候,小T有E的体力。
接下来每一天有一个任务,这个任务小T可以付出任意的非负整数体力去完成,并且,每一天的结束的时候,小T会增加R的体力。当然体力是不可能超出E的,也就是说,如果当前体力+R大于E,那么恢复完之后的体力依旧是E。毫无疑问,体力是不可能小于0的。
每个任务会有一个价值V[],一个任务的收获就是这个任务的价值乘上付出的体力。
你要帮帮小T,使他最大化 “所有任务的收获之和”, 方便他继续的高富帅!
最后,我们的口号是“烧死GFS~”。

Input

第一行一个正整数case,表示数据的组数。
对于每一组数据,第一行有三个正整数E,R,N,表示的是能量上限,恢复值,和这个月的天数。第二行有N个非负整数表示V[1]-V[N]。

Output

对于一组数据,一行输出最大化的收获之和。

Sample Input

1
5 2 2
2 1

Sample Output

12

HINT

第一天用5的体力,接下来恢复2点体力,再用光。
Can<=10,N<=500000,E<=10^6.所有的输入非负,并且,V<=10^6。

题解

考试的时候水了一个dp,得了30,基本没怎么做过分治的题,所以真的不是很好想……

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 500010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll lg[maxn];
int rmq[maxn][40];
ll a[maxn];
ll n,lim,rec;
void RMQ()
{
    for(ll j=1;(1<<j)<=n;j++)
    for(ll i=1;i+(1<<j)-1<=n;i++)
    rmq[i][j]=a[rmq[i][j-1]]>a[rmq[i+(1<<(j-1))][j-1]]?rmq[i][j-1]:rmq[i+(1<<(j-1))][j-1];
}
ll ans;
ll ask(ll l,ll r)
{
    ll t=lg[r-l+1];
    return a[rmq[l][t]]>a[rmq[r-(1<<t)+1][t]]?rmq[l][t]:rmq[r-(1<<t)+1][t];
}
void solve(ll l,ll r,ll st,ll ed)
{
    if(l>r) return;
    ll k=ask(l,r);ll t,b;
    if(st+(k-l)*rec<=lim) t=st+(k-l)*rec;
    else t=lim,solve(l,k-1,st,lim);
    if((r-k+1)*rec<ed) b=ed-(r-k+1)*rec;
    else b=0,solve(k+1,r,rec,ed);
    ans+=(t-b)*a[k];    
}
int main()
{
    int T;T=read();
    for(ll i=2;i<maxn;i++) lg[i]=lg[i>>1]+1;
    while(T--)
    {
        lim=read();rec=read();n=read();
        for(int i=1;i<=n;i++) 
        {
            a[i]=read();
            rmq[i][0]=i;
        }
        RMQ();
        solve(1,n,lim,rec);
        cout<<ans<<endl;
        ans=0;
    }
}```