結果
| 問題 |
No.952 危険な火薬庫
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:17:43 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,370 bytes |
| コンパイル時間 | 761 ms |
| コンパイル使用メモリ | 81,708 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:18:52 |
| 合計ジャッジ時間 | 4,442 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | TLE * 1 -- * 22 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// Use long long for costs and sums to avoid overflow, as intermediate sums and squares can be large.
using ll = long long;
// Define a large constant to represent infinity.
// The maximum possible cost could be roughly (N * max(A_i))^2.
// For N=3000 and max(A_i)=100000, this is (3000 * 100000)^2 = (3e8)^2 = 9e16.
// This fits within a 64-bit signed long long (which goes up to approx 9e18).
// Using 4e18 as INF provides a safe margin.
const ll INF = 4e18;
int main() {
// Use fast I/O operations.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of doors
cin >> N;
vector<ll> A(N); // Danger values for each door
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
// Calculate prefix sums of danger values.
// S[k] will store the sum of danger values for doors 1 through k.
// S[0] is 0. S has size N+1.
vector<ll> S(N + 1, 0);
for (int i = 0; i < N; ++i) {
// A[i] corresponds to door i+1. S[i+1] stores sum up to door i+1.
S[i + 1] = S[i] + A[i];
}
// Initialize the DP table.
// dp[i][j] will store the minimum total danger cost using exactly j open doors
// among the first i doors (doors numbered 1 to i).
// The table dimensions are (N+1) x (N+1).
// dp[i] row corresponds to the state after considering door i.
vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, INF));
// Base case: Using 0 open doors always results in a total danger cost of 0.
// This is true for any prefix length i, including the empty prefix (i=0).
for (int i = 0; i <= N; ++i) {
dp[i][0] = 0;
}
// Fill the DP table using dynamic programming.
// Iterate through each door index i from 1 to N.
for (int i = 1; i <= N; ++i) {
// Iterate through the number of open doors j required, from 1 up to i.
// It's impossible to open more doors than available, so j <= i.
for (int j = 1; j <= i; ++j) {
// Option 1: Door i is kept closed.
// In this case, the minimum cost is the same as the minimum cost using j open doors
// among the first i-1 doors. We inherit the value from dp[i-1][j].
dp[i][j] = dp[i - 1][j];
// Option 2: Door i is opened.
// If door i is open, it must be the rightmost door of some connected component [L, i].
// We need to consider all possible start positions L for this component.
// The length of this component is k = i - L + 1.
// Iterate over possible lengths k for this component ending at i.
// The length k must be at least 1 and cannot exceed the total number of open doors j.
for (int k = 1; k <= j; ++k) {
int L = i - k + 1; // Calculate the start index L (1-based) of the component.
// The component [L, i] uses k doors. The remaining j-k doors must be chosen
// from the prefix of doors 1 to L-2. This is because door L-1 must be closed
// (or not exist if L=1) to ensure [L, i] is a maximal component starting at L.
int prev_doors_count = j - k; // Number of doors needed from the prefix 1..(L-2).
// The state in the DP table that corresponds to the prefix 1..(L-2) is indexed by L-2.
// dp[prev_prefix_idx][prev_doors_count] gives the minimum cost for that subproblem.
int prev_prefix_idx = L - 2;
ll prev_cost; // Stores the minimum cost from the subproblem dp[L-2][j-k].
// Determine the cost from the prefix 1..(L-2)
if (prev_prefix_idx < 0) {
// If L=1 or L=2, the prefix 1..(L-2) is effectively empty.
// An empty prefix can only satisfy the requirement of using 0 doors.
if (prev_doors_count == 0) {
prev_cost = 0; // Cost is 0 if 0 doors needed for empty prefix.
} else {
// It's impossible to use a positive number of doors in an empty prefix.
prev_cost = INF;
}
} else {
// If L > 2, the prefix is 1..(L-2). This corresponds to dp table index prev_prefix_idx = L-2.
// Check if the required number of doors `prev_doors_count` is non-negative.
if (prev_doors_count >= 0) {
// Retrieve the precomputed minimum cost for this subproblem.
// If the state dp[prev_prefix_idx][prev_doors_count] was impossible to reach,
// the DP table would store INF.
prev_cost = dp[prev_prefix_idx][prev_doors_count];
} else {
// It's impossible to need a negative number of doors.
prev_cost = INF;
}
}
// If the subproblem state dp[L-2][j-k] is reachable (i.e., cost is not INF)
if (prev_cost != INF) {
// Calculate the danger cost of the current component [L, i].
// The sum of danger values A_p for p from L to i is S[i] - S[L-1].
ll current_comp_sum = S[i] - S[L - 1];
// The danger cost is the square of the sum.
ll current_comp_cost = current_comp_sum * current_comp_sum;
// Update dp[i][j]: take the minimum of the current value (from Option 1 or previous Option 2 iterations)
// and the cost obtained by forming component [L, i] (prev_cost + current_comp_cost).
dp[i][j] = min(dp[i][j], prev_cost + current_comp_cost);
}
} // End loop over k (component length)
} // End loop over j (number of doors)
} // End loop over i (door index)
// After filling the DP table, dp[N][k] contains the minimum cost using exactly k doors among all N doors.
// Output the results for each k from 1 to N.
for (int k = 1; k <= N; ++k) {
cout << dp[N][k] << "\n";
}
return 0;
}