//time时间内 dp[i][j]前i个人中完成j个A任务后最多能完成多少B任务// dp[i][j] = max(dp[i][j],(time – k*a[i])/b[i]+dp[i-1][j-k]);//由于time越大，dp[i][j]越大,故可以用二分找到最小的time的值#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 210;const int inf = 0x7fffffff;int dp[maxn][maxn];//time时间内 dp[i][j]前i个人中完成j个A任务后最多能完成多少B任务int N,X,Y;int a[maxn],b[maxn];int DP(int time){ memset(dp,-1,sizeof(dp)); for(int j = 0;j*a[1] <= time && j<=X;j++) dp[1][j] = (time-a[1]*j)/b[1]; for(int i = 2;i <= N;i++) for(int j = 0;j <= X;j++) for(int k = 0;k*a[i] <= time && k <= j;k++) { if(dp[i-1][j-k] == -1) continue; dp[i][j] = max(dp[i][j],(time – k*a[i])/b[i]+dp[i-1][j-k]); } if(dp[N][X] >= Y) return 1; else return 0;}int bit(int left,int right){ while(left <= right) { int middle = (left+right)/2; if(DP(middle)) right = middle – 1; if(!DP(middle)) left = middle + 1; } return left;}int main(){ //freopen("in.txt","r",stdin); int T; int cas = 0; scanf("%d", &T); while(T–) { scanf("%d%d%d",&N,&X,&Y); int mi = inf ; for(int i = 1;i <= N;i++) { scanf("%d%d",&a[i],&b[i]); mi = min(a[i]*X+b[i]*Y,mi); } printf("Case %d: ",++cas); printf("%d\n",bit(1,mi)); } return 0;}
，一个人的期望值越大，心理承受力就会越小，就越经受不住失败的打击，
