本题利用单调队列优化dp
状态转移依然不错
f[i][j]表示第i个木匠刷到j总共的报酬
将题中的木匠按si进行排序,只会更新j>=si的,保证没有后效性
f[i][j]=max(f[i-1][j],f[i][j-1]);表示可以i木匠不刷或者当前的木板不刷
f[i][j]=max( f[i][j],f[i-1][k]+p[i]*(j-k) ) j>=si,j-k>=li;
当i固定时
寻找k的过程可以用单调队列优化
当j++时k的选择范围增加了1
将方程中与k有关的部分放到单调队列中
维护一个f[i-1][k]-p[i]*k单减,k单增的队列,即可完成转移
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 16010, M = 105;
struct painter
{
int si,pi,li;
}per[M];
int n,m,f[M][N];
bool cmp(painter a,painter b)
{
return a.si<b.si;
}
int main()
{
// freopen("123.txt","r",stdin);
cin >> n >> m;
for(int i = 1;i<=m;i ++)
scanf("%d%d%d",&per[i].li,&per[i].pi,&per[i].si);
sort(per+1,per+1+m,cmp);
for(int i=1;i<=m;i++)
{
deque<PII> q1;
for(int j=0;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(j>=per[i].si)
{
while(q1.size() && q1.front().second<j-per[i].li)q1.pop_front();
if(q1.size())f[i][j]=max(f[i][j],q1.front().first+per[i].pi*j);
}
else
{
while(q1.size() && q1.back().first<=f[i-1][j]-per[i].pi*j)q1.pop_back();
q1.push_back({f[i-1][j]-per[i].pi*j,j});
}
}
}
cout<<f[m][n];
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
zc
$qp$
兹磁