C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 6736K, 提交时间: 2020-04-10 11:06:45

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
	int L,P,S;
}a[110];
int n,m,dp[110][16010],q[16010];
bool operator<(node A,node B)
{
	return A.S<B.S;
}
int cal(int i,int k)
{
	return dp[i-1][k]-a[i].P*k;
}
int main()
{
	cin>>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+1+m);
	for(int i=1;i<=m;i++)
	{
		int head=1,tail=0;//初始化单调队列
		for(int k=max(0,a[i].S-a[i].L);k<=a[i].S-1;k++)//最初的候选集合插入队列 
		{
			while(head<=tail&&cal(i,q[tail])<=cal(i,k))
				tail--;
			q[++tail]=k;
		}
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//不粉刷时的转移
			if(j>=a[i].S)//粉刷第k+1~j块木板时的转移 
			{
				while(head<=tail&&q[head]<j-a[i].L)//排除队头不合法转移 
					head++;
				if(head<=tail)
					dp[i][j]=max(dp[i][j],cal(i,q[head])+a[i].P*j);
			} 
		} 
	}
	cout<<dp[m][n]<<endl;
	return 0;
} 

C++(g++ 7.5.0) 解法, 执行用时: 10ms, 内存消耗: 6660K, 提交时间: 2023-02-02 12:05:31

#include<iostream>
#include<algorithm>
using namespace std;

struct worker
{
    int l,p,s;
}a[105];

int n,m,f[105][16005],q[16005];

bool operator<(worker a,worker b) { return a.s<b.s;}

inline int calc(int i,int k) { return f[i-1][k]-a[i].p*k; }

int main(void)
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i].l>>a[i].p>>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(a[i].s-a[i].l,0);k<=a[i].s-1;k++)
        {
            while(l<=r&&calc(i,k)>=calc(i,q[r])) 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) continue;
            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);
        }
    }
    cout<<f[m][n]<<endl;
    return 0;
}

C++ 解法, 执行用时: 12ms, 内存消耗: 7040K, 提交时间: 2021-10-09 00:47:45

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int f[110][20000],n,m;
struct node
{
    int l,p,s;
}a[200010];
bool cmp(node a,node b)
{
    return a.s<b.s;
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].p>>a[i].s;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        f[i][j]=max(f[i-1][j],f[i][j-1]);
        if(j>=a[i].s&&j-a[i].s+1<=a[i].l)
        {
            for(int l=max(1,j-a[i].l+1);l<=a[i].s;l++)
            f[i][j]=max(f[i][j],f[i-1][l-1]+(j-l+1)*a[i].p);
        }
    }
    cout<<f[n][m]<<endl;
}