#PU1477. USACO 2025 January Contest, Platinum — Problem 2. Shock Wave

    ID: 1564 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan25来源:usaco.orgscoring:equal_test_cases二分答案

USACO 2025 January Contest, Platinum — Problem 2. Shock Wave

USACO 2025 January Contest, Platinum — Problem 2. Shock Wave

题目描述

Bessie is experimenting with a powerful hoof implant that has the ability to create massive shock waves. She has NN (2≤N≤1052 \leq N \leq 10^5) tiles lined up in front of her, which require powers of at least p0,p1,…,pN−1p_0,p_1,\dots,p_{N-1} to break, respectively (0≤pi≤10180 \leq p_i \leq 10^{18}). Bessie can apply power by punching a specific tile but due to the strange nature of her implant, it will not apply any power to the tile she punches. Instead, if she chooses to punch tile xx once, where xx is an integer in [0,N−1][0,N-1], it applies ∣i−x∣|i-x| power to tile ii for all integers ii in the range [0,N−1][0,N-1]. This power is also cumulative, so applying 22 power twice to a tile will apply a total of 44 power to the tile. Please determine the fewest number of punches required to break all the tiles.

输入格式

The first line contains TT (1≤T≤1001 \leq T \leq 100) representing the number of test cases. Line 2t2t contains a single integer NN, the number of tiles in test case tt. Line 2t+12t+1 contains NN space separated numbers p0,p1,…,pN−1p_0,p_1, \ldots, p_{N-1} representing that tile ii takes pip_i power to be broken. It is guaranteed that the sum of all NN in a single input does not exceed 5⋅1055\cdot 10^5.

输出格式

TT lines, the iith line representing the answer to the iith test case.

数据范围

(见题面原文)

样例

样例 1

6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000
2
3
2
4
4
2000000000000000000
For the first test, the only way for Bessie to break all the tiles with two
punches is to punch $0$ twice, applying total powers of $[0,2,4,6,8]$
respectively.
For the second test, one way for Bessie to break all the tiles with three
punches is to punch $0$, $2$, and $4$ one time each, applying total powers of
$[6,5,4,5,6]$ respectively.
For the third test, one way for Bessie to break all the tiles with two punches
is to punch $0$ and $1$ one time each, applying total powers of $[1,1,3,5,7]$
respectively.