任务调度分配题两道 POJ 1973 POJ 1180（斜率优化复习）

POJ 1973

这道题以前做过的。今儿重做一次。由于每个程序员要么做A,要么做B，可以联想到0/1背包（谢谢N巨）。这样，可以设状态

dp[i][j]为i个程序员做j个A项目同时，最多可做多少个B项目。枚举最后一个程序员做多少个A项目进行转移（0/1）。

dp[i][j]=max{dp[i-1][k]+(time-(j-k)*a[i])/b[i]}。于是，二分时间time进行判定即可。

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int dp[110][110];

int a[110],b[110];

int n,m;

bool slove(int time){

	memset(dp,-1,sizeof(dp));

	for(int i=0;i<=m;i++){

		if(time-i*a[1]<0) continue;

		dp[1][i]=(time-i*a[1])/b[1];

	}

	for(int i=2;i<=n;i++){

		for(int j=0;j<=m;j++){

			for(int k=0;k<=j;k++){

				if(dp[i-1][k]<0||time-(j-k)*a[i]<0) continue;

				dp[i][j]=max(dp[i][j],dp[i-1][k]+(time-(j-k)*a[i])/b[i]);

			}

		}

	}

	//bool flag=false;

	for(int i=0;i<=n;i++){

		if(dp[i][m]>=m) return true;

	}

	return false;

}

int main(){

	int T;

	scanf("%d",&T);

	while(T--){

		int l=0,r=0;

		scanf("%d%d",&n,&m);

		for(int i=1;i<=n;i++){

			scanf("%d%d",&a[i],&b[i]);

			r+=(a[i]*m+b[i]*m);

		}

		int ans=100000000;

		while(l<=r){

			int mid=(l+r)>>1;

			if(slove(mid)){

				ans=mid;

				r=mid-1;

			}

			else l=mid+1;

		}

		printf("%d\n",ans);

	}

	return 0;

}

POJ 1180

开始时设了二维的数组。一看范围，就知道不行了。。

可以很容易就看出是DP了。可以倒过来设状态dp[i]表示加入i任务，从i任务到n任务完成所需要的时间。

dp[i]=min{dp[j]+（s+tsum[i]-tsum[j]）*fsum[i]}//i之后的第一个分组是从j开始，枚举。

这样还不足够。可以用斜率来优化。假设j<p。如果对于决策i,j更优于p，则有dp[j]+(s+tsum[i]-tsum[j])*fsum[i]<dp[p]+(s+tsum[i]-tsum[j])*fsum[i]。化简有

dp[j]-dp[p]<(tsum[j]-tsum[p])*fsum[i]。可以看到是斜率k=g[j,p]=(dp[j]-dp[p])/(tsum[j]-tsum[p])<fsum[i]，j优于p。

对于k<j<p。如果有g[k,j]<g[j,p]。则j必定是可以不要的。因为当g[k,j]<s时，明显k优于j。否则g[k,j]>s，有s<g[k,j]<g[j,p]。说明，k不优于j,j不优于p。

于是，j是可以不要的。

斜率减少。因而可以去掉j。在这里，我们要维护的是斜率的下凸，如：g[k,j]>g[j,p]。这样，对于j点，如果j点可选，则其前面的点均可以不需要了。因为斜率是下凸，会直到某个斜率大于fsum[i]，才会选到最优。

用一个单调队列维护即可。

#include <iostream>

#include <cstdio>

#include <algorithm>

#define LL __int64

using namespace std;

int t[10010],f[10010];

LL ts[10010],fs[10010];

int que[10010],head,tail;

LL dp[10010];

int main(){

	int n,s;

	while(scanf("%d",&n)!=EOF){

		head=tail=0;

		scanf("%d",&s);

		for(int i=1;i<=n;i++){

			scanf("%d%d",&t[i],&f[i]);

		}

		dp[n+1]=0; ts[n+1]=fs[n+1]=0;

		for(int i=n;i>=1;i--){

			ts[i]=(ts[i+1]+t[i]);

			fs[i]=(fs[i+1]+f[i]);

		}

		head=tail=0;

		dp[n+1]=0;

		que[tail++]=n+1;

		dp[n]=(s+ts[n])*fs[n];

		que[tail++]=n;

		for(int i=n-1;i>=1;i--){

			while(head<tail-1&&dp[que[head+1]]-dp[que[head]]<=(ts[que[head+1]]-ts[que[head]])*fs[i])

			head++;

			dp[i]=dp[que[head]]+(s+ts[i]-ts[que[head]])*fs[i];

			while(head+1<tail&&(dp[i]-dp[que[tail-1]])*(ts[que[tail-1]]-ts[que[tail-2]])<=(dp[que[tail-1]]-dp[que[tail-2]])*(ts[i]-ts[que[tail-1]]))

			tail--;

			que[tail++]=i;

		}

		printf("%I64d\n",dp[1]);

	}

	return 0;

}

巴特西

任务调度分配题两道 POJ 1973 POJ 1180（斜率优化复习）

最新文章

热门文章