題目鏈接

https://www.luogu.com.cn/problem/P1800

思路

對于大于等于最優解的天數，一定能使公司交付軟件。對于小于最優解的天數，一定無法使公司交付軟件。所以考慮二分答案$x$。

定義$f[i][j]$表示前$i$個人做了$j$個軟件$1$的模塊時，他們最多還能多做多少個軟件$2$的模塊。

因為每一個人都是相對獨立的，所以轉移方程為：

$f[i][j]=max(f[i?1][k]+?\frac{x?d1[i]\times (j?k)}{d2[i]}?)$。

時間復雜度：$O(n{m}^{2}lo{g}_{2}2e4)$。

代碼

#include <bits/stdc++.h>using namespace std;#define int long longconst int N = 1e2 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, m;
int a[N], b[N], f[N][N];
bool check(int x)
{memset(f, -inf, 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 <= j; k++){if (x >= a[i] * (j - k))f[i][j] = max(f[i][j], f[i - 1][k] + (x - a[i] * (j - k)) / b[i]);}}}return f[n][m] >= m;
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i];}int low = 1, high = 2e4;while (low < high){int mid = low + high >> 1;if (check(mid)){high = mid;}else low = mid + 1;}cout << high << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}