TIOJ 2135：背包問題
TIOJ 2135 ：背包問題 題目大意：有 $N$ 個物品跟一個容量 $W$ 的背包，每個物品有 $w,v,c$，代表大小 $w$、價值 $v$，除了整個拿以外，也可以花 $c$ 的錢拿 $v\times\frac{w'}{w}$，有 $Q$ 次修改，每次會改某個物品的 $c$，修改完回答最大收益。 解法：發現最多只會花費一個物品的 $c$，可以分治求出不包含某個物品的 $dp$ 值，枚舉切多少後用 $\text{multiset}$ 存答案。 $\text{Code：}$ # include <bits/stdc++.h> using namespace std ; const int N = 1005 ; const int M = 2005 ; int n, m, q; double ans[N]; vector < int > op[M]; multiset < double > ms; int w[N], v[N], c[N], dp[M]; void divide ( int l, int r) { if (l == r) { if (l == 1 ) ms.insert(max(dp[m], w[ 1 ] <= m ? dp[m - w[ 1 ]] + v[ 1 ] : 0 )); ans[l] = 0 ; for ( int i = 1 ; i <= min(m, w[l]); i++) ans[l] = max(ans[l], dp[m - i] + ( double ) v[l] * i / w[l]); ms.insert(ans[l] - c[l]); return ; } int mid = (l + r) / 2 ; for ( int i = 0 ; i <= m; i++) op[i].emplace_back(dp[i]); for ( int i = mid + 1 ; i <= r; i++) for ( int j = m; j >= w[i]; j--) dp[j] = ma