[Codeforces 1579G] Minimal Coverage | dp最小区间覆盖

简介: 题意: 给出n个线段,以及一个无限大的坐标轴,第一个线段以0为起点进行放置,后面的线段必须以前一个的终点为起点放置,这就有两种方式,向左向右

You are given n lengths of segments that need to be placed on an infinite axis with coordinates.
The first segment is placed on the axis so that one of its endpoints lies at the point with coordinate 0. Let’s call this endpoint the “start” of the first segment and let’s call its “end” as that endpoint that is not the start.
The “start” of each following segment must coincide with the “end” of the previous one. Thus, if the length of the next segment is d and the “end” of the previous one has the coordinate x, the segment can be placed either on the coordinates [x−d,x], and then the coordinate of its “end” is x−d, or on the coordinates [x,x+d], in which case its “end” coordinate is x+d.
The total coverage of the axis by these segments is defined as their overall union which is basically the set of points covered by at least one of the segments. It’s easy to show that the coverage will also be a segment on the axis. Determine the minimal possible length of the coverage that can be obtained by placing all the segments on the axis without changing their order.
Input
The first line contains an integer t ( 1 ≤ t ≤ 1000 ) — the number of test cases.
The next 2t lines contain descriptions of the test cases.
The first line of each test case description contains an integer n ( 1 ≤ n ≤ 1 0 4 ) — the number of segments. The second line of the description contains n space-separated integers a i ( 1 ≤ a i ≤ 1000 ) — lengths of the segments in the same order they should be placed on the axis.
It is guaranteed that the sum of n over all test cases does not exceed 10 4 .
Output
Print t lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the minimal possible length of the axis coverage.
Example
inputCopy

相关文章
|
算法
poj 2479 Maximum sum(求最大子段和的延伸)
看完最大连续子段和 的 dp算法 这个很容易理解,我用dplift[i]保存第1到第i个之间的最大子段和,dpright[i]保存第i到第n个之间的最大子段和,最终结果就是dplift[i]+dpright[i+1]中最大的一个。
47 0
|
开发框架 .NET
poj 3468 A Simple Problem with Integers线段树区间修改
题目意思很简单,有N个数,Q个操作, Q l r 表示查询从l到r 的和,C l r v 表示将从l到r 的值加上v,明显的线段树,不知道线段树的人肯定暴力,肯定超时,哈哈!!
30 0
|
机器学习/深度学习
Codeforces1499——C. Minimum Grid Path(思维+分奇偶+贪心)
Codeforces1499——C. Minimum Grid Path(思维+分奇偶+贪心)
91 0
|
机器学习/深度学习
AtCoder Beginner Contest 215 F - Dist Max 2 (二分 单调队列)
AtCoder Beginner Contest 215 F - Dist Max 2 (二分 单调队列)
132 0
|
机器学习/深度学习 人工智能 算法
CF1446D Frequency Problem(思维 前缀和 根号分治 双指针)
CF1446D Frequency Problem(思维 前缀和 根号分治 双指针)
91 0
|
机器学习/深度学习 人工智能 算法
[Codeforces 1579G] Minimal Coverage | dp最小区间覆盖
题意: 给出n个线段,以及一个无限大的坐标轴,第一个线段以0为起点进行放置,后面的线段必须以前一个的终点为起点放置,这就有两种方式,向左向右
184 0
Optimal Coin Change(完全背包计数)
题目描述 In a 10-dollar shop, everything is worthy 10 dollars or less. In order to serve customers more effectively at the cashier, change needs to be provided in the minimum number of coins. In this problem, you are going to provide a given value of the change in different coins.
90 0
|
算法 Java C语言
LeetCode 200:岛屿数量 Number of Islands
题目: 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
818 0
|
算法
动态规划法(八)最大子数组问题(maximum subarray problem)
问题简介   本文将介绍计算机算法中的经典问题——最大子数组问题(maximum subarray problem)。所谓的最大子数组问题,指的是:给定一个数组A,寻找A的和最大的非空连续子数组。
1765 0