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

题意：

K个人对N块木板涂色，每个人初始站在一块木板前（不重复），每人最多只能涂包含所站木板的连续l个木板或一个木板也不涂。给出每人最多涂的木块数l,涂一快木板的工钱p，站的木板s。求这群人最多共获得多少工钱。 题解： dp[i][j]代表前i个粉刷匠粉刷完成至多前j个木板的最大利益，状态转移有三种： 1、不需要第i个粉刷匠，即前i-1个粉刷匠完成前j个木板的工作：dp[i][j]=dp[i-1][j] 2、不需要粉刷第j块木板，即前i个粉刷匠完成前j-1个木板的工作：dp[i][j]=dp[i][j-1] 3、前i-1个粉刷匠粉刷到了第k块木板，然后第i个粉刷匠从第k+1开始一直粉刷到第j个木板：dp[i][j]=max(dp[i][j],dp[i-1][k]+p[i](j-k))

前两种直接转移即可，第三种必须要用些优化才能节约时间dp[i-1][k]+p[i](j-k)=dp[i-1][k]-p[i]*k+p[i]*j，其中p[i]*j对固定dp[i][j]是固定的，即dp[i-1][k]-p[i]*k越大越好，所以可以用优先队列将所有能够通过第三种方式更新dp[i][j]储存起来，能够更新需要满足两个条件k<Si且k+Li>=j，所以可以首先将[Si-Li，Si-1]区间的值预处理出来，并在每次选取优先队列中元素时判断它是否满足k+Li>=j即可（如果不满足，因为j是递增的，它以后也不会满足，所以可以直接pop掉）

AC代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef pair
        
         PA;const int maxn=16000+10;const int maxk=100+10;int k,n;int dp[maxk][maxn];struct People{ int L,P,S; bool operator <(const People &A)const { return S
         
          ,less
          
            >que; for(int j=max(0,S-L);j
           
            j||S+L-1
           
          
         
        
       
      
     
    
   

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