P2365 任务安排 题解

link

P2365 任务安排

Solve

这道题有弱化版和强化版，这道题是弱化版

我们很容易能想到一个(DP)方程(F[p][i])表示前(i)个取了(p)段的最优解，于是转移方程

[F[p][i]=min(F[p-1][j]+(ST[i]+past S)ast (SF[i]-SF[j])) ]

这个转移方程是(O(n^3))的考虑怎么优化

对于每次转移时间都要加上一个(p)我们提前记录下(p)的费用

在每一次转移方程时能预判到后面(j-N)的时间都要加上(p)

于是转移方程就能化到(O(n^2))了，可以过了

[F[i]=min(F[j]+ST[i]ast (SF[j]-SF[i])+S ast (SF[N]-SF[j])) ]

但是仅仅优化到这里是不够了

观察到可以用斜率优化来优化到(O(n))

转化一下式子

[(S+ST[i])ast SF[j]+(dp[i]-ST[i]ast SF[i]- Sast SF[i])=(dp[j]) ]

观察到(S+ST{i])单调递增，(SF[i])单调递增

所以用单调队列就好了

Code

(O(n^2))

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int N,S,t[maxn],f[maxn],s_t[maxn],s_f[maxn],dp[maxn];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f; 
}
int main(){
	freopen("P2365.in","r",stdin);
	freopen("P2365.out","w",stdout);
	N=read();S=read();
	for(int i=1;i<=N;i++)t[i]=read(),f[i]=read();
	for(int i=1;i<=N;i++)s_t[i]=s_t[i-1]+t[i],s_f[i]=s_f[i-1]+f[i];
	memset(dp,63,sizeof dp);dp[0]=0;
	for(int i=1;i<=N;i++)
	for(int j=0;j<=i;j++){
		dp[i]=min(dp[j]+s_t[i]*(s_f[i]-s_f[j])+S*(s_f[N]-s_f[j]),dp[i]);
	}
	printf("%d
",dp[N]);
	return 0;
}

(O(n))

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=10005;
int N,S,s_f[maxn],s_t[maxn],hed=1,til,F[maxn],Q[maxn];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f; 
}
int X(int j){return s_f[j];}
int Y(int j){return F[j]-S*s_f[j];}
long double calc(int i,int j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}

int main(){
	freopen("P2365.in","r",stdin);
	freopen("P23650.out","w",stdout);
	N=read(),S=read();
	for(int i=1;i<=N;i++)s_t[i]=s_t[i-1]+read(),s_f[i]=s_f[i-1]+read();
	Q[++til]=0;
	for(int i=1;i<=N;i++){
		while(hed<til&&calc(Q[hed],Q[hed+1])<=((s_t[i])))++hed;
		int j=Q[hed];F[i]=F[j]+s_t[i]*(s_f[i]-s_f[j])+S*(s_f[N]-s_f[j]);
		while(hed<til&&calc(Q[til-1],Q[til])>=calc(Q[til-1],i))--til;
		Q[++til]=i;
	}
	printf("%d
",F[N]);
	return 0;
}