[小明打联盟][斜率/单调队列 优化dp][背包]

时间：2022-02-09 10:20:44

链接：https://ac.nowcoder.com/acm/problem/14553
来源：牛客网

题目描述

小明很喜欢打游戏，现在已知一个新英雄即将推出，他同样拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：

1.乌鸦坐飞机 释放时间：x 固定伤害值：a

2.蜘蛛吃耳屎 释放时间：y 固定伤害值：b

3.饿狼前进  释放时间：z 固定伤害值：c

他还有一个大招，其释放的时间是一个区间【L,R】，可以在区间内任意时间点释放出技能，其如果在L+i时刻释放技能，其能够打出的伤害值为:temp+A*i

这里temp值表示技能的基础伤害（同时也就是在时刻L释放技能的伤害值）,A是一个常数。

小明很喜欢研究连招使得在有限的时间内打出最高的伤害，现在他想要在T长度单位时间内打出最高的伤害，问这个最大伤害值。

输入描述:

本题包含多组数据。
输入格式为：
T
x a
y b
z c
L R temp A
数据范围：
1<=T<=1e5
1<=x,y,z,L,R<=T
L<=R
<=a,b,c,temp,A<=1e5
输出描述:
输出包含一行，输出能够打出的最高伤害值。
示例1
输入
8

3 1

2 3

1 3

3 3 3 3
输出
24
备注:
大招：蓄力时间最短L秒，最多R秒。无限次释放，释放之后照成的伤害是随着时间增加的
蓄力L秒释放能够造成Temp的伤害
蓄力L+1秒释放能够造成Temp+1*A的伤害
依次类推

题意：小明有三个小技能和一个大招，每个小技能消耗ai的时间，打出bi的伤害，大招的基础伤害为temp，基础时间为L,大招可以蓄力，得到的伤害为temp+(T-L)*A,其中T为大招的时间，上限为R，求总时间为t打出的最高伤害
题解：对于三个小技能可以直接使用普通的背包dp，而对于大招，如果暴力地把大招时间拆成L，L+1....R，那么复杂度将是O(N^2)，很明显会超时，而观察到对大招来说dp[i]=max(dp[j]+temp+A*(i-L-j))，所以对于j>k， 如果 j 相对于k更优，那么(dp[j]+temp+A*(i-L-j)) - (dp[k]+temp+A*(i-L-k)) > 0，所以有dp[j]-dp[k]>A*(j-k)，可以使用斜率优化dp，而由于这里的A为常数，和 i 无关，所以可以直接知道当前点是否最优，不需要维护凸包，也就是可以不使用斜率优化dp，而使用单调队列优化dp(斜率优化dp和单调队列优化dp区别就在插入新点时前者是维护凸包后者是维护单调队列)

斜率优化dp

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<map>

using namespace std;

//#define io_test

#define debug(x) cout<<x<<"####"<<dp[x][0]<<"##"<<dp[x][1]<<endl;

typedef long long ll;

ll dp[],pq[];

int main()

{

#ifdef io_test

    freopen("in.txt","r",stdin);

    freopen("out.txt","w",stdout);

#endif // io_test

    //int n,m;

    int t;

    while(scanf("%d",&t)==){

        ll x,y,z,a,b,c;

        //queue<struct pot>pq;

        scanf("%lld%lld%lld%lld%lld%lld",&x,&a,&y,&b,&z,&c);

        ll l,r,temp,A;

        scanf("%lld%lld%lld%lld",&l,&r,&temp,&A);

        int head=;

        int tail=;

        for(int i=;i<=t;i++){

            dp[i]=dp[i-];

            if(i>=x){

                dp[i]=max(dp[i],dp[i-x]+a);

            }

            if(i>=y){

                dp[i]=max(dp[i],dp[i-y]+b);

            }

            if(i>=z){

                dp[i]=max(dp[i],dp[i-z]+c);

            }

            if(i>=l){

                while((head+<=tail&&(i-pq[head]>r||(dp[pq[head+]]-dp[pq[head]]>(pq[head+]-pq[head])*A))))head++;

                if(head<=tail){

                    dp[i]=max(dp[i],dp[pq[head]]+temp+A*(i-pq[head]-l));

                }

                while(tail-head>=&&(dp[i-l+]-dp[pq[tail]])*(pq[tail]-pq[tail-])>(i-l+-pq[tail])*(dp[pq[tail]]-dp[pq[tail-]]))tail--;//维护凸包

                ++tail;

                pq[tail]=i-l+; 

            }

        }

        printf("%lld\n",dp[t]);

    }

    return ;

}

单调队列优化dp

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 #include<map>

 using namespace std;

 //#define io_test

 #define debug(x) cout<<x<<"####"<<dp[x][0]<<"##"<<dp[x][1]<<endl;

 typedef long long ll;

 ll dp[],pq[];

 int main()

 {

 #ifdef io_test

     freopen("in.txt","r",stdin);

     freopen("out.txt","w",stdout);

 #endif // io_test

     //int n,m;

     int t;

     while(scanf("%d",&t)==){

         ll x,y,z,a,b,c;

         //queue<struct pot>pq;

         scanf("%lld%lld%lld%lld%lld%lld",&x,&a,&y,&b,&z,&c);

         ll l,r,temp,A;

         scanf("%lld%lld%lld%lld",&l,&r,&temp,&A);

         int head=;

         int tail=;

         for(int i=;i<=t;i++){

             dp[i]=dp[i-];

             if(i>=x){

                 dp[i]=max(dp[i],dp[i-x]+a);

             }

             if(i>=y){

                 dp[i]=max(dp[i],dp[i-y]+b);

             }

             if(i>=z){

                 dp[i]=max(dp[i],dp[i-z]+c);

             }

             if(i>=l){

                 while((head+<=tail&&(i-pq[head]>r||(dp[pq[head+]]-dp[pq[head]]>(pq[head+]-pq[head])*A))))head++;

                 if(head<=tail){

                     dp[i]=max(dp[i],dp[pq[head]]+temp+A*(i-pq[head]-l));

                 }

                 while(tail>=head&&(dp[i-l+]-dp[pq[tail]])>A*(dp[i-l+]-dp[pq[tail]]))tail--;//维护单调队列

                 ++tail;

                 pq[tail]=i-l+; 

             }

         }

         printf("%lld\n",dp[t]);

     }

     return ;

 }

这题还有一个背包的写法，因为大招的伤害和时间的关系是条直线，所以最后的结果一定是若干小技能+若干次不蓄力大招+若干次蓄满力大招+一次不满的大招(注意只会使用一次不满的大招，这点决定了可以直接背包而不会T掉)，也就是说真正需要暴力枚举的大招时间只有一次，也就是那次没有满的大招，所以复杂度就是O(N)

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 #include<map>

 using namespace std;

 //#define io_test

 #define debug(x) cout<<x<<"####"<<dp[x][0]<<"##"<<dp[x][1]<<endl;

 typedef long long ll;

 ll dp[],pq[];

 int main()

 {

 #ifdef io_test

     freopen("in.txt","r",stdin);

     freopen("out.txt","w",stdout);

 #endif // io_test

     //int n,m;

     int t;

     while(scanf("%d",&t)==){

         ll x,y,z,a,b,c;

         //queue<struct pot>pq;

         scanf("%lld%lld%lld%lld%lld%lld",&x,&a,&y,&b,&z,&c);

         ll l,r,temp,A;

         scanf("%lld%lld%lld%lld",&l,&r,&temp,&A);

         int head=;

         int tail=;

         for(int i=;i<=t;i++){

             dp[i]=dp[i-];

             if(i>=x){

                 dp[i]=max(dp[i],dp[i-x]+a);

             }

             if(i>=y){

                 dp[i]=max(dp[i],dp[i-y]+b);

             }

             if(i>=z){

                 dp[i]=max(dp[i],dp[i-z]+c);

             }

             if(i>=l){

                 dp[i]=max(dp[i],dp[i-l]+temp);

             }

             if(i>=r){

                 dp[i]=max(dp[i],dp[i-r]+temp+A*(r-l));

             }

         }

         for(int i=l;i<=r;i++){//未满的大招只有一次，所以只进行一次枚举更新

             if(t>=i)dp[t]=max(dp[t],dp[t-i]+temp+A*(i-l));

         }

         printf("%lld\n",dp[t]);

     }

     return ;

 }

相关文章