poj1821

题目链接
大意:给你n个木块,k个人。每个人有三个参数 l , p , s l,p,s l,p,s,分别表示每个人最多加工的木块数,每个人加工一个木块的贡献,每个人加工木块区间必须包含的 木块编号
思路:先看题,考虑 d p [ i ] [ j ] dp[i][j] dp[i][j]表示第i个人加工到j号木块的最大贡献, T [ i ] T[i] T[i]表示加工i个木块的最大贡献
然后我们每次遍历i转移就是
d p [ i ] [ j ] = m a x ( T [ x ] + ( j x ) p [ i ] . p ) , x [ p [ i ] . s l , p [ i ] . s ) j [ p [ i ] . s , p [ i ] . s + p [ i ] . l 1 ) dp[i][j]=max(T[x]+(j-x)*p[i].p) ,x\in[p[i].s-l,p[i].s)。j\in[p[i].s,p[i].s+p[i].l-1) dp[i][j]=max(T[x]+(jx)p[i].p),x[p[i].sl,p[i].s)j[p[i].s,p[i].s+p[i].l1)
T [ k ] = m a x ( T [ k ] , d p [ i ] [ k ] ) , k [ 0 , n ] T[k]=max(T[k],dp[i][k]),k\in[0,n] T[k]=max(T[k],dp[i][k]),k[0,n]
然后我们发现转移是选 T [ x ] x p [ i ] . p T[x]-x*p[i].p T[x]xp[i].p最大的进行转移,然后我们可以维护一个递减的单调队列,放当前的值,和位置下标。
转移的时候弹出不合法的元素,然后直接取队头的进行转移即可,时间复杂度 O ( n k ) . O(nk). O(nk).

#include<iostream>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <stdlib.h>
#include <string.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int n,k;
struct uzi
{
	LL l,p,s;
}p[N];
int cmp(uzi x,uzi y){
	return x.s<y.s;
}
LL f[111][16123],T[16123];
pair<LL,int>Q[N];
int l,r;
int main(){
	while(cin>>n>>k){
		for(int i=1;i<=k;i++)cin>>p[i].l>>p[i].p>>p[i].s;
		LL ans=0;
		sort(p+1,p+1+k,cmp);
		for(int i=1;i<=k;i++){
			l=0,r=0;
			Q[0].se=-1e9;
			for(int j=p[i-1].s;j<=p[i-1].s+p[i-1].l-1&&j<=n;j++)T[j]=max(T[j],f[i-1][j]);
			for(int j=max(0ll,p[i].s-p[i].l);j<p[i].s;j++){
				LL tmp=T[j]-j*p[i].p;
				while(l<r&&tmp>=Q[r].fi)r--;
				pair<LL,int>na;
				na.fi=tmp;
				na.se=j;
				Q[++r]=na;
			}
			for(int j=p[i].s;j<=p[i].s+p[i].l-1&&j<=n;j++){
				while((l<r&&Q[l].se<j-p[i].l))l++;
				f[i][j]=max(Q[l].fi+j*p[i].p,f[i][j]);
				ans=max(ans,f[i][j]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
头像
10-09 19:35
门头沟学院 Java
洛必不可达:java的竞争激烈程度是其他任何岗位的10到20倍
点赞 评论 收藏
分享
牛客279957775号:铁暗恋
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务