http://acm.nyist.net/JudgeOnline/problem.php?pid=229

#include<iostream> #include<cstdio> #include<cstring>using namespace std;const int MAXN = 110;int Ap[MAXN]; int Bp[MAXN]; int dp[MAXN];//dp[i]表示完成i個工作A，之后還能完成多少個工作B int n,m;int MAX(int a, int b) {return a > b ? a : b; }int slove( int mid ) {int i,j,k;memset(dp, -1, sizeof(dp));for(i = 0; i <= m; ++i)//第一個人完成i個A，還可以完成多少個Bif(mid >= i*Ap[1])dp[i] = (mid-i*Ap[1])/Bp[1];elsebreak;if(dp[m] >= m)//如果第一個人完成A之后，還有足夠的時間來完成B，那么就說明這個mid時間是可以的return 1;//如果剩下的時間不足以完成B，或者給定mid的時間完不成A， 剩下的就是背包思想for(i = 2; i <= n; ++i){//既然第一個人不能在給定的mid時間內完成兩個任務，那么接下來在讓其他人上,看前i是否可以完成任務for(j = m; j >= 0; --j){for(k = 0; k <= j && k*Ap[i] <= mid; ++k){//如果第i個人可以完成k份工作A，并且前i-1個人已完成了j-k個工作A，(即是否可以留更多的時間來做更多的工作)那么前i個工人還可以完成多少份工作？if(dp[j-k] != -1)dp[j] = MAX(dp[j], dp[j-k]+(mid-k*Ap[i])/Bp[i]);}}if(dp[m] >= m)//如果前i(包括i)個工人完成A之后還能完成B，那么返回1，說明mid滿足return 1;}return 0; }int main() {int i,T;scanf("%d", &T);while(T--){int maxtime = 0;scanf("%d%d",&n,&m);for(i = 1; i <= n; ++i){scanf("%d%d",&Ap[i],&Bp[i]);maxtime = MAX(maxtime, MAX(Ap[i], Bp[i]));}int L = 0,R = (maxtime*m) << 1;while(L < R){int mid = (L + R)>>1;if(slove(mid))//如果給定的mid時間一直都滿足，那么繼續收縮區間，直到找到一個最小的時間R = mid;elseL = mid + 1;}printf("%d\n",L);}return 0; }

總結

以上是生活随笔為你收集整理的nyoj 229的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。