1677：软件开发
时间限制: 1000 ms 内存限制: 131072 KB
【题目描述】
一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成\(m\)个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的所用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序，求出公司最早能在什么时候交付软件。
【输入】
输入文件第一行包含两个由空格隔开的整数\(n\)和\(m\)。
接下来的\(n\)行每行包含两个用空格隔开的整数\(d_1\)和\(d_2\)，\(d_1\)表示该技术人员完成第一个软件中的一个模块所需的天数，\(d_2\)表示该技术人员完成第二个软件中的一个模块所需的天数。
【输出】
输出文件仅有一行包含一个整数\(d\)，表示公司最早能于\(d\)天后交付软件。
【输入样例】
3 20
1 1
2 4
1 6
【输出样例】
18
【数据规模】
对于100%的数据，\(1≤n≤100，1≤m≤100，1≤d_1,d_2≤100\)。
【样例说明】
最快的方案是第一个技术人员完成第二个软件的18个模块，用时18天，第三个技术人员完成第一个软件的18个模块，用时18天，其余的模块由第二个技术人员完成，用时12天，做完所有的模块需要18天。如果第一个技术人员完成第二个软件的17个模块，第三个技术人员完成第一个软件的17个模块，其余的模块由第二个技术人员完成，需要用时18天，做完所有模块仍然需要18天，所以少于18天不可能做完所有模块。
题目最先想到的就是DP。但是f[i][x][y]前i个人最早几天能完成x个软件1的模块和软件2的y个模块。
很明显超时。
然后把f去掉一维，f[i][x]表示前i个人在完成x个程序1的模块的情况下最多能完成多少个第二个程序的模块，当然时间要二分一下，从而去判断。f[i][x]=max(f[i-1][y]+(mid-fir[i]*(x-y))/sec[i])
很长时间不写DP了，需要注意边界！！！
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int f[maxn][maxn];
int n,m;
int fir[maxn],sec[maxn];
int ans;
bool pd(int mid)
{
memset(f,-0x7f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;++i)f[i][0]=f[i-1][0]+mid/sec[i];
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
for(int k=j;k>=0;--k)
if(mid>=(j-k)*fir[i])
{
f[i][j]=max(f[i][j],f[i-1][k]+(mid-(j-k)*fir[i])/sec[i]);
}
}
}
return f[n][m]>=m;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d%d",&fir[i],&sec[i]);
int l=0,r=10000;
while(l<=r)
{
int mid=(l+r)>>1;
if(pd(mid))ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
return 0;
}