結果
| 問題 |
No.1947 質より種類数
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:22 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,147 ms / 2,000 ms |
| コード長 | 6,648 bytes |
| コンパイル時間 | 875 ms |
| コンパイル使用メモリ | 83,580 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:18 |
| 合計ジャッジ時間 | 6,041 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 37 |
ソースコード
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
// Using namespace std to simplify code writing (e.g., std::vector -> vector)
using namespace std;
// Define long long type alias for potentially large satisfaction values
// This helps avoid integer overflow issues.
typedef long long ll;
// State structure to store elements in the monotonic queue (deque).
// Each element corresponds to a state processed at a particular multiple 'q'.
// It stores 'q' and the calculated value 'val' which is used for optimization.
// Specifically, val = dp[q * v_i + r] - q * w_i
struct State {
int q; // The multiple index q
ll val; // The calculated value V(q) = dp[q * v_i + r] - q * w_i
};
int main() {
// Faster I/O operations by decoupling C++ standard streams from C stdio
ios_base::sync_with_stdio(false);
// Untie cin from cout to potentially speed up input operations
cin.tie(NULL);
int N; // Number of item types
ll V; // Total budget
ll C; // Coefficient for the reward based on the number of distinct item types purchased
cin >> N >> V >> C;
// Vectors to store item properties: v[i] is the price, w[i] is the value for item type i
vector<ll> v(N), w(N);
for (int i = 0; i < N; ++i) {
cin >> v[i] >> w[i];
}
// DP table: dp[j] stores the maximum satisfaction achievable with a budget of exactly j
// Initialize all entries to 0. dp[0] = 0 means 0 satisfaction with 0 budget (buy nothing).
// Other dp[j] = 0 initially represents the minimum possible satisfaction (non-negative).
vector<ll> dp(V + 1, 0);
// Iterate through each item type to build the DP solution
for (int i = 0; i < N; ++i) {
// According to constraints, v[i] >= 1, so price is positive.
// If the problem allowed v[i] <= 0, we might need a check here.
// Example: if (v[i] <= 0) continue;
// Create a temporary DP table (dp_new) initialized with the current state of dp.
// This is crucial because the calculations for item 'i' must be based on the results
// from items 0 to i-1. Using dp_new prevents updates within the current item's loops
// from affecting subsequent calculations for the same item, which would violate the
// logic of the multiple choice knapsack problem formulation.
vector<ll> dp_new = dp;
// Apply the monotonic queue optimization technique.
// This requires processing budgets based on their remainder modulo v[i].
// Iterate through all possible remainders r from 0 to v[i]-1.
for (int r = 0; r < v[i]; ++r) {
// Initialize an empty deque (double-ended queue) for this remainder r.
// The deque will store State objects, maintaining the monotonic property needed for optimization.
deque<State> Q;
// Iterate through multiples q = 0, 1, 2, ...
// such that the current budget level current_j = q * v[i] + r does not exceed V.
for (int q = 0; ; ++q) {
ll current_j = (ll)q * v[i] + r; // Calculate current budget level
if (current_j > V) {
break; // Stop if the budget exceeds the limit V
}
// If the queue is not empty, we can potentially update dp_new[current_j].
// The front element of the queue Q.front() corresponds to the state 'x'
// that maximizes V(x) = dp[x*v_i+r] - x*w[i] among the relevant previous states x < q.
if (!Q.empty()) {
ll max_prev_V = Q.front().val; // Get the maximum V(x) value from the front
// Calculate the potential satisfaction achieved by choosing item type i.
// The formula derived from the optimization is max_prev_V + C + q * w[i].
// This represents the maximum satisfaction achievable by transitioning from a previous state 'x'
// (captured by max_prev_V) and purchasing item type i (at least once, total k = q-x items).
// The total satisfaction contribution is C + k*w[i].
// Adding this to the base satisfaction dp[x*v_i+r] and simplifying algebraically gives this formula.
ll potential_satisfaction = max_prev_V + C + (ll)q * w[i];
// Update the satisfaction for budget current_j if this path yields a higher value.
// It compares against the value already in dp_new[current_j], which could be:
// 1. The value from the previous DP state `dp[current_j]` (i.e., not using item `i`).
// 2. A value updated by processing a previous remainder `r'` for the same item `i`.
dp_new[current_j] = max(dp_new[current_j], potential_satisfaction);
}
// Calculate V(q) = dp[current_j] - q * w[i].
// This calculation must use the DP state *before* considering item i.
// `dp[current_j]` holds the values from the previous iteration (items 0 to i-1).
ll current_Vq = dp[current_j] - (ll)q * w[i];
// Maintain the monotonic property of the queue: values `val` should be strictly decreasing.
// Remove elements from the back of the queue whose `val` are less than or equal to `current_Vq`.
// This ensures that the queue only stores potentially optimal states.
while (!Q.empty() && Q.back().val <= current_Vq) {
Q.pop_back();
}
// Add the current state represented by {q, current_Vq} to the back of the queue.
Q.push_back({q, current_Vq});
}
}
// After processing all remainders for the current item i, update the main DP table `dp`
// with the newly computed values from `dp_new`. This prepares `dp` for the next iteration (next item).
dp = dp_new;
}
// The final answer is the maximum satisfaction value found in the DP table across all possible
// budget levels from 0 to V. Since satisfaction might not increase monotonically with budget
// (e.g., spending more might force suboptimal choices), we must check all budgets.
ll max_satisfaction = 0;
for (ll j = 0; j <= V; ++j) {
max_satisfaction = max(max_satisfaction, dp[j]);
}
// Output the final maximum satisfaction value.
cout << max_satisfaction << endl;
return 0; // Indicate successful execution
}