| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P183PROC - ROUND 3C - Đôi bạn thân |
Dark Magican và QQMM là đôi bạn thân, cả hai đều rất thích tựa game Liên Quân Mobile và thường xuyên leo rank cùng nhau. Trong trận đấu quyết định để lên cao thủ của Dark Magician, vì tính hay troll bạn bè, QQMM đã phá game khiến Dark Magician không lên được cao thủ. Dark Magician rất tức giận nên đã block QQMM. QQMM cảm thấy hối hận nên đã đến xin Dark Magician tha lỗi. Dark Magician tính thù dai nên yêu cầu QQMM phải giải được bài toán anh đưa ra thì mới tha lỗi. Vốn thông minh từ nhỏ nên QQMM đã nhận lời ngay. Tuy nhiên, bài toán Dark Magician đưa ra không hề dễ dàng, một mình QQMM không thể nghĩ ra được nên đành cầu cứu các bạn PTIT. Các bạn hãy giúp QQMM lấy lại tình bạn nhé! Bài toán như sau :
Một dãy số được gọi là đẹp nếu nó là dãy số tăng dần (tức là với mọi i, j mà i < j thì ai < aj). Cho một dãy số a có n phần tử. Trong mỗi lượt bạn có thể chọn bất kì phần tử nào trong dãy và tăng hoặc giảm nó đi 1 đơn vị. Mục đích là làm cho dãy số trở nên đẹp. Bạn được phép thay đổi các phần tử thành bất kì giá trị nào, kể cả thành âm hoặc bằng 0. Nhiệm vụ của bạn là tìm ra số lượt tối thiểu để biến đổi dãy số đã cho thành dãy đẹp.
Input
Dòng đầu tiên chứa số nguyên n – độ dài của dãy số (1 ≤ n ≤ 3000).
Dòng tiếp theo chứa n số nguyên ai (1 ≤ ai ≤ 109).
Output
Số nguyên duy nhất – đáp án bài toán của Dark Magician.
Example
Test 1:
Input: 2
1 10000 Output: 0
Test 2:
Input:
5
1 1 1 2 3
Output:
3
| Được gửi lên bởi: | adm |
| Ngày: | 2018-03-16 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
