[HDOJ3433 A Task Process]【二分答案】【dp验证】

【题目大意】

有n个人，X件A工作，Y件B工作。然后第i个人做一件A工作需要Ta[i]，做一件B工作需要Tb[i]。最后输出，完成给定的工作至少需多少时间。

【算法分析】

就是二分答案然后dp。 F[i][j]表示决策完第i个人，A工作完成了j件，B工作最多能完成多少件？然后转移比较沙茶，那么略去。

【其他】

1Y。这几天被GDOI的作业弄得半死。。。该做的基本做了~不管了。现在开始做多校联赛的题。。。这题是送分的A题。。。

【CODE】

#include

#include

#include #define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
const int N=55;
const int INF=100000000;
int n,X,Y;
int Ta[N],Tb[N];
int F[N][205];

void init(){
     scanf("%d%d%d",&n,&X,&Y);
     for (int i=1;i<=n;i++)
       scanf("%d%d",&Ta[i],&Tb[i]);
}

bool Can(int Limit){
     int i,j,k;
     for (i=0;i<=n;i++)
       for (j=0;j<=X;j++)
         F[i][j]=-INF;
     F[0][0]=0;
     for (i=1;i<=n;i++)
       for (j=0;j<=X;j++)
         for (k=0;k<=j;k++)
           if ((j-k)*Ta[i]<=Limit)
           F[i][j]=max(F[i][j],F[i-1][k]+(Limit-(j-k)*Ta[i])/Tb[i]);
     return F[n][X]>=Y;
}

void solve(){
     int l=0,r=400000,mid;
     while (l           mid=l+r>>1;
           if (Can(mid)) r=mid;
                    else l=mid+1;
     }
     printf("%dn",l);
}

int main(){
    int Tc,i;
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        printf("Case %d: ",i);
        init();
        solve();
    }
}