正題

題目鏈接:http://poj.org/problem?id=1821

---

題目大意

有n個木板,m個工人，每個木板只能被粉刷一次，第i個工人如果刷的話必須刷木板SiSi，連續的不超過LiLi的，沒一塊PiPi。

---

解題思路

用fi,jfi,j表示前j塊木板，前i個工人最大價值，然后如果什么都不做就是fi?1,jfi?1,j，也可以空著不刷fi,j?1fi,j?1。然后我們就在1～Li1～Li的范圍內找到

fi,j=maxj?Li≤k≤Si?1{fi?1,j+Pi?(j?k)}(j≥Si)fi,j=maxj?Li≤k≤Si?1{fi?1,j+Pi?(j?k)}(j≥Si)
然后用單調隊列維護k就好了。

---

code

#include<cstdio> #include<queue> #include<algorithm> using namespace std; struct node{int l,p,s; }a[110]; int n,m,f[110][16010]; deque<int> q; bool cmp(node x,node y) {return x.s<y.s;} int calc(int i,int k){return f[i-1][k]-a[i].p*k; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s);sort(a+1,a+m+1,cmp);for(int i=1;i<=m;i++){while(!q.empty())q.pop_back();for(int k=max(0,a[i].s-a[i].l);k<=a[i].s-1;k++){while(!q.empty()&&calc(i,q.back())<=calc(i,k)) q.pop_back();q.push_back(k);}//加入元素for(int j=1;j<=n;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);//啥都不干if(j>=a[i].s){while(!q.empty()&&q.front()<j-a[i].l) q.pop_front();//維護區域if(!q.empty()) f[i][j]=max(f[i][j],calc(i,q.front())+a[i].p*j);//統計答案}}}printf("%d",f[m][n]); }

總結

以上是生活随笔為你收集整理的POJ1821-Fence【单调队列,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。