记录编号	320429	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	ZXCVBNM_1	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2016-10-12 01:04:38	内存使用	0.36 MiB

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
int f[110][110],d1[110],d2[110],n,m;
bool Judge(int val)
{
    int i,j,k;
    memset(f,0,sizeof(f));//f[i][j]表示当前到了第i个人,在第一个软件做到第j个模块,第二个软件最多做到多少
    //f[i][j]=max(f[i][j],f[i-1][k]+(val-d1[i]*(j-k))/d2[i]); (k<=j)
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)f[i][j]=-INF;
    }
    f[0][0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            for(k=0;k<=j;k++)
            {
                if((val-d1[i]*(j-k))>=0)f[i][j]=max(f[i][j],f[i-1][k]+(val-d1[i]*(j-k))/d2[i]);
            }
        }
    }
    if(f[n][m]>=m)return true;
    else return false;
}
int main()
{
    freopen("time.in","r",stdin);
    freopen("time.out","w",stdout);
    int i,l,r,mid,ans;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d %d",&d1[i],&d2[i]);
    l=0;r=10000;ans=0;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(Judge(mid)==true){ans=mid;r=mid-1;}
        else l=mid+1;
    }
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}