本文共 1529 字，大约阅读时间需要 5 分钟。

这种dp见过,但还是完全没思路呢…

$首先状态太多,考虑用数组的值储存状态,具体的意思是$

$dp[i][j]表示做完前i个任务,A机器花费j时间,B机器花费的最小时间$

$那么转移也非常显然,每次枚举A机器的时间s$

$当第i个任务由A机器完成时$

$$dp[i][s]=dp[i-1][s-a]$$

$当第i个任务由B机器完成时$

$$dp[i][s]=dp[i-1][s]+b$$

$当第i个任务被共同完成时$

$$dp[i][s]=dp[i-1][s-c]+c$$

$因为时间空间比较紧,加了一点优化在代码里$

#include 
   
    using namespace std;int a,b,c,dp[2][30009],sumn,n;int main(){	cin >> n;	memset(dp,127,sizeof(dp));	dp[0][0]=0;	int start=0;	for(int i=1;i<=n;i++)	{		int t=(i&1);		scanf("%d%d%d",&a,&b,&c);		memset(dp[t],127,sizeof(dp[t]) );		int inf=dp[t][0];		sumn+=max(a,max(b,c) );		for(int j=start;j<=sumn;j++)		{			if( a&&j-a>=0 )				dp[t][j]=min( dp[t][j],dp[t^1][j-a] );			if( b )				dp[t][j]=min( dp[t][j],dp[t^1][j]+b );			if( c&&j-c>=0 )				dp[t][j]=min( dp[t][j],dp[t^1][j-c]+c);		}		for(int j=start;j<=sumn;j++ )		{			if( dp[i&1][j]==inf )	start++;			else	break;		}	}	int ans=1e9;	for(int i=0;i<=30000;i++)		ans=min( ans,max( dp[n&1][i],i) );	cout << ans;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108260811 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！