【题解】Fence(单调队列)

╰+攻爆jí腚メ 2021-11-18 01:16 311阅读 0赞

## 【题解】Fence(单调队列) ##

[POJ - 1821][]

### 题目大意 ###

有\\(k\\)个粉刷匠，每个粉刷匠一定要粉刷某个位置\\(S\_i\\)，一个粉刷匠可以粉刷至多\\(l\_i\\)个位置(必须连续\\(l\_i\\)互不相同)，一个粉刷匠粉刷一个位置要收\\(p\_i\\)元，问怎么安排可以使得粉刷匠赚的钱最大。

\\(dp(i,j)\\)考虑了前\\(i\\)个人，考虑了前\\(j\\)个位置的最大值，转移是这样的:  
\\\[ dp(i,j)=\\max\\\{\\max\\\{dp(i-1,k)+(j-k)\\times p\_i\\\},dp(i-1,j),dp(i,j-1)\\\},k\\in\[j-l\_i,s\_i) \\\]  
按照讨论把第二个\\(\\max\\)变一下  
\\\[ max\\\{dp(i-1,k)+(j-k)\\times p\_i\\\}=\\max\\\{dp(i-1,k)-kp\_i\\\}+jp\_i \\\]  
现在问题就变成如何维护\\(\\max\\\{dp(i-1,k)-kp\_i\\\}\\)

单调队列就好了。注意一些细节：

*  \\(\\max\\\{dp(i-1,j),dp(i,j-1)\\\}\\) 要在转移完毕后继承。
 *  \\(k\\in \[j-l\_i,s\_i)\\)
 *  \\(dp(0,\\forall x)=dp(\\forall x,0)=0\\)(初始化)

目标:\\(dp(k,n)\\)。

//@winlere #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; inline int qr(){ register int ret=0,f=0; register char c=getchar(); while(c<48||c>57)f|=c==45,c=getchar(); while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar(); return f?-ret:ret; } const int maxn=1.6e4+5; struct NODE{ int l,p,s; NODE(){l=p=s=0;} inline void scan(){l=qr();p=qr();s=qr();} inline bool operator <(const NODE&a)const{return s<a.s;} }data[101]; int dp[101][maxn]; int n,k; deque < int > q; int main(){ n=qr();k=qr(); memset(dp,0xcc,sizeof dp); memset(dp[0],0,sizeof dp[0]); for(register int t=1;t<=k;++t) data[t].scan(),dp[t][0]=0; sort(data+1,data+k+1); for(register int t=1;t<=k;++t){ q.clear();q.push_back(0); for(register int i=1;i<data[t].s;++i){ while(q.size()&&q.back()+data[t].l<data[t].s) q.pop_back(); while(q.size()&&(dp[t-1][q.front()]-q.front()*data[t].p<=dp[t-1][i]-i*data[t].p)) q.pop_front(); q.push_front(i); } for(register int i=data[t].s;i<=min(n,data[t].s+data[t].l-1);++i){ while(q.size()&&q.back()+data[t].l<i) q.pop_back(); if(q.size()) dp[t][i]=max(dp[t][i],dp[t-1][q.back()]+(i-q.back())*data[t].p); } for(register int i=1;i<=n;++i) dp[t][i]=max(dp[t][i],max(dp[t-1][i],dp[t][i-1])); } cout<<dp[k][n]<<endl; return 0; }

转载于:https://www.cnblogs.com/winlere/p/10990710.html

[POJ - 1821]: https://vjudge.net/problem/10478/origin