upc 地球发动机线性dp + 二分-白红宇的个人博客

发布日期：2021-09-25 23:57:35 浏览次数：8 分类：技术文章

本文共 1462 字，大约阅读时间需要 4 分钟。

地球发动机

时间限制: 1 Sec 内存限制: 128 MB

题目描述

“啊，地球，我的流浪地球……”——《流浪地球》

在一条直线上，从左到右排列着n台地球发动机，每台发动机有着固定的位置坐标Ai和功率Pi，保证Ai<Ai+1。此外，由于地球发动机的特性，每台发动机还有一个参数Xi，如果一台发动机运行，则坐标范围在[Ai,Ai+Xi]的其它发动机就无法运行。现在你想让正在运行的发动机总功率最大，请输出这个总功率。

输入

第一行一个整数n,意义如上所述。

接下来n行，每行三个整数Ai,Pi,Xi,意义如题面所述。

输出

一行一个整数，表示可能的最大功率。

样例输入 Copy

2 5 1

5 4 3

8 10 3

9 2 2

样例输出 Copy

提示

对于20%的数据，n≤10，0<Ai,Pi,Xi≤10；

对于50%的数据，n≤2000，0<Ai,Pi,Xi≤105；

对于100%的数据，n≤105，0<Ai,Pi,Xi≤109。

一开始没看完题为了快点直接写了个区间贪心，结果发现区间还带权值，让后就放弃了贪心的做法，开始考虑dp。

f [ i ] [ j ] 表示当前选到第 i 个发动机，j 表示选或者不选。

让后就一直正向做dp，wa到自闭了。找师傅问了下，结果是要反向做dp，让后每个点转移状态是从前面转移过来，这是为了防止产生后效性，也就是说从前面转移的时候，需要考虑前面的发动机能不能让他熄火，时间复杂度剧增，而且情况还有很多，所以可以考虑反向dp，每次选择这个点 i 的时候用二分找到位置大于 a [ i ] + x [ i ] 的点的 f [ t ] [ 0 ] 和 f [ t ] [ 1 ] 中大的一个状态转移过来，加上 p [ i ] 即可。不选择这个点的时候，直接从 f [ i + 1 ] 的两个状态转移过来即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;int a[N],p[N],x[N];LL f[N][2];LL ans;int main(){ // ios::sync_with_stdio(false);// cin.tie(0); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&p[i],&x[i]); for(int i=n;i>=1;i--) { int t=upper_bound(a+1,a+1+n,a[i]+x[i])-a; f[i][1]=max(f[t][1],f[t][0])+p[i]; f[i][0]=max(f[i+1][1],f[i+1][0]); } printf("%lld\n",max(f[1][0],f[1][1])); return 0;}

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105679967 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：upc 马拉松比赛 dp

下一篇：upc 电话网络二分+最短路

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章