803 . 電車遊戲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

17.2% (5/29)

Tags

apcsc apcsc-dp

Description

小峰在玩電車遊戲，這個遊戲規則相當簡單。玩家一共要移動 $N$ 次，每次抽出一個數字 $a_i$，小峰可以選擇往左走或往上走 $a_i$ 公尺，小峰需要最小化遊戲結束時所在位置與起點的距離，請問這個最短距離為何？

Input Format

輸入第一行是一個整數 $N$，表示移動次數。
第二行是 $N$ 個整數 $a_1, a_2, \dots, a_N$，表示每次移動的距離。

輸入保證 $1\le N\le 1000$，$1\le a_i\le 500$。

Output Format

輸出一行一個整數，表示最短移動距離的平方。

Sample Input 1

3
1 5 7

Sample Output 1

85

Sample Input 2

6
10 7 6 9 2 15

Sample Output 2

1201

Hints

Problem Source

ZeroJudge

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~17 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
Submit
Back to Top