题意

Description

Input

Output

Sample Input

8 4
3 2 2
3 2 3
3 3 5
1 1 7 

Sample Output

17

Hint

Source

K个人对N块木板涂色，每个人初始站在一块木板前（不重复），每人最多只能涂包含所站木板的连续l个木板或一个木板也不涂。给出每人最多涂的木块数l,涂一快木板的工钱p，站的木板s。求这群人最多共获得多少工钱。

分析

参照mousehao001的题解。

dp[i][j]表示前i个人对前j块木板操作的最大收益。

核心状态转移方程：
dp[i][j]=max(dp[i][j-1],dp[i-1][k]+P[i].p*(j-k),dp[i-1][j])
max(0,P[i].s-P[i].l)<=k<min(P[i].s-1,j) ?k=0表示前i-1个人在玩泥巴。。

显然直接做就是枚举i,j,k。

观察dp[i-1][k]+P[i].p*(j-k)=(dp[i-1][k]-P[i].p*k)+P[i].p*j

在枚举k的时候,P[i].p*j的值已经确定不用考虑，只需要找出使(dp[i-1][k]-P[i].p*k)最大的k就行了，又观察到这个式子的值不与j相关，也就是说在枚举k之前我们就可以通过某种方法找出这个k，即：构造递减的 单调队列 维护k值。

时间复杂度\(O(MN)\)

代码

#include<iostream>
#include<algorithm>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=16001,M=101;
struct rec{int L,P,S;}a[M];
bool operator<(co rec&a,co rec&b) {return a.S<b.S;}
int n,m,f[M][N],q[N];
int calc(int i,int k){
    return f[i-1][k]-a[i].P*k;
}
int main(){
    read(n),read(m);
    for(int i=1;i<=m;++i) read(a[i].L),read(a[i].P),read(a[i].S);
    sort(a+1,a+m+1);
    for(int i=1;i<=m;++i){
        int l=1,r=0;
        for(int k=max(0,a[i].S-a[i].L);k<=a[i].S-1;++k){
            while(l<=r&&calc(i,q[r])<=calc(i,k)) --r;
            q[++r]=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(l<=r&&q[l]<j-a[i].L) ++l;
                if(l<=r) f[i][j]=max(f[i][j],calc(i,q[l])+a[i].P*j);
            }
        }
    }
    printf("%d\n",f[m][n]);
    return 0;
}

POJ1821 Fence

原文：https://www.cnblogs.com/autoint/p/10724913.html