P1800 software 二分优化 DP
P1800 software
很明显的二分，用 DP 写 check()。
对于 check(t)，转移方程：
\(dp_{i,j}\) 表示前 \(i\) 个人在做 \(j\) 个项目 1 的情况下最多能做的项目二的个数。
\[dp_{i,j} = \max_{k=1}^j dp_{i-1,k} + (t - a_i \times (j-k)) \div b_i
\]
答案为：
\[dp_{n,m} \ge m
\]
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[110],b[110];
int dp[110][110];
bool check(int t){
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=j;k++){
int lft=t-(j-k)*a[i];
if(lft>=0&&dp[i-1][k]>0)dp[i][j]=max(dp[i][j],dp[i-1][k]+lft/b[i]);
}
}
}
return dp[n][m]>m;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
int l=1,r=1e9,mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cout<<r<<endl;
}