题目地址
思路： dp[i][A] 表示第i件物品，花费A机器A的时间且花费B机器dp[i][A]的时间的最小值 dp[i][A] = min(dp[i-1][A-a[i]]，dp[i-1][A]+b[i]);
1：dp[i-1][A-a[i]] 表示第i件物品用于A机器处理； 2：dp[i-1][A] + b[i] 表示用于B机器处理，当前A机器还是要处理A的时间 3：最后一个最优的时间为 min{max(A,dp[n][A]),....,...} 4： 第一维可以省略，像01背包那样 #include<bits/stdc++.h> using namespace std; #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 100010; const int INF = 0x3f3f3f3f; int a[210],b[210],dp[N]; /* dp[i][A] 表示第i件物品，花费A机器A的时间且花费B机器dp[i][A]的时间的最小值 dp[i][A] = min(dp[i-1][A-a[i]]，dp[i-1][A]+b[i]); 1：dp[i-1][A-a[i]] 表示第i件物品用于A机器处理； 2：dp[i-1][A] + b[i] 表示用于B机器处理，当前A机器还是要处理A的时间 3：最后一个最优的时间为 min{max(A,dp[n][A]),....,...} */ signed main(){ IOS; #ifdef ddgo freopen("in.txt","r",stdin); #endif memset(dp,INF,sizeof(dp)); dp[0] = 0; int n,sum = 0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i]; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++) for(int j=sum;j>=0;j--) if(j >= a[i]) dp[j] = min(dp[j-a[i]],dp[j]+b[i]); else dp[j] += b[i]; int res = INF; for(int i=0;i<=sum;i++) res = min(res,max(i,dp[i])); cout<<res<<endl; }