P1800 software_NOI導(dǎo)刊2010提高（06）
標簽 二分答案
難度 普及/提高-
題目描述
一個軟件開發(fā)公司同時要開發(fā)兩個軟件，并且要同時交付給用戶，現(xiàn)在公司為了盡快完成這一任務(wù)，將每個軟件劃分成m個模塊，由公司里的技術(shù)人員分工完成，每個技術(shù)人員完成同一軟件的不同模塊的所用的天數(shù)是相同的，并且是已知的，但完成不同軟件的一個模塊的時間是不同的，每個技術(shù)人員在同一時刻只能做一個模塊，一個模塊只能由一個人獨立完成而不能由多人協(xié)同完成。一個技術(shù)人員在整個開發(fā)期內(nèi)完成一個模塊以后可以接著做任一軟件的任一模塊。寫一個程序，求出公司最早能在什么時候交付軟件。
輸入輸出格式
輸入格式：
輸入文件第一行包含兩個由空格隔開的整數(shù)n和m，其中1<=n<=100，1<=m<=100，接下來的n行每行包含兩個用空格隔開的整數(shù)d1和d2，d1表示該技術(shù)人員完成第一個軟件中的一個模塊所需的天數(shù)，d2表示該技術(shù)人員完成第二個軟件中的一個模塊所需的天數(shù)，其中1<= d1,d2<=100。
輸出格式：
輸出文件僅有一行包含一個整數(shù)d，表示公司最早能于d天后交付軟件。
輸入輸出樣例
輸入樣例#1：
3 20
1 1
2 4
1 6
輸出樣例#1：
18
說明
【樣例】
最快的方案是第一個技術(shù)人員完成第二個軟件的18個模塊，用時18天，第三個技術(shù)人員完成第一個軟件的18個模塊，用時18天，其余的模塊由第二個技術(shù)人員完成，用時12天，做完所有模塊需要18天。如果第一個技術(shù)人員完成第二個軟件的17個模塊，第三個技術(shù)人員完成第一個軟件的17個模塊，其余的模塊由第二個技術(shù)人員完成，需要用時18天，做完所有模塊仍然需要18天，所以少于18天不可能做完所有模塊。

/* 二分答案+DP檢驗. 這題一看就是二分嘛. 然后檢驗不大好想. 然后偷著看了看題解orz. 一開始也想這樣DP來著但是狀態(tài)不好定義. f[i][j]表示前i個人做j個第一項目任務(wù) 還能做的第二項目任務(wù)的數(shù)量. 然后有f[i][j]=max(f[i][j],f[i-1][j-k]+(x-a[i]*k)/b[i]). */ #include<iostream> #include<cstdio> #include<cstring> #define MAXN 101 using namespace std; int max1,n,m,a[MAXN],b[MAXN],ans,tot,f[MAXN][MAXN]; int read1() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; } bool check(int x) { memset(f,-127/3,sizeof f); f[0][0]=0; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=min(x/a[i],j);k++) f[i][j]=max(f[i][j],f[i-1][j-k]+(x-a[i]*k)/b[i]); return f[n][m]>=m; } void erfen(int l,int r) { int mid; while(l<=r) { mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%d",ans); } int main() { n=read1(),m=read1(); for(int i=1;i<=n;i++) a[i]=read1(),b[i]=read1(), max1+=a[i]+b[i]; erfen(1,max1*n); return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/nancheng58/p/10068170.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1800 software_NOI导刊2010提高（06）(二分答案+DP检验)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。