编程介的小学生 2020-01-16 11:46 采纳率: 20.5%
浏览 146

Dynamic Programming? 动态编程的问题

Problem Description
Dynamic Programming, short for DP, is the favorite of iSea. It is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable to problems exhibiting the properties of overlapping sub-problems which are only slightly smaller and optimal substructure.
Ok, here is the problem. Given an array with N integers, find a continuous subsequence whose sum’s absolute value is the smallest. Very typical DP problem, right?

Input
The first line contains a single integer T, indicating the number of test cases.
Each test case includes an integer N. Then a line with N integers Ai follows.

Technical Specification
1. 1 <= T <= 100
2. 1 <= N <= 1 000
3. -100 000 <= Ai <= 100 000

Output
For each test case, output the case number first, then the smallest absolute value of sum.

Sample Input
2
2
1 -1
4
1 2 1 -2

Sample Output
Case 1: 0
Case 2: 1

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
    • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
    • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
    • ¥30 3天&7天&&15天&销量如何统计同一行
    • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
    • ¥15 vs2019中数据导出问题
    • ¥20 云服务Linux系统TCP-MSS值修改?
    • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
    • ¥20 怎么在stm32门禁成品上增加查询记录功能