Бодолт илгээх | Бүх бодолтууд | Шилдэг бодолтууд | Жагсаалт руу буцах |
RGB7605 - Бага төлөх гишгүүрүүд |
Хүү шатаар өгсөхдөө 2 янзаар урагшилна. Зогсож байгаа гишгүүрийн дараагийнх эсвэл 1 гишгүүр алгасаад дараагийнх дээр нь очно. Гэтэл нэгэн нөхөр шатны гишгүүрүүдийг төлбөртэй болгосноор асуудал үүсгэв. Сүүлийн гишгүүрт хамгийн багадаа хэдийг төлж хүрэх вэ? Хамгийн бага төлбөр төлж явахын тулд хэд хэддүгээр гишгүүрүүдээр дамжих вэ? Бага төлбөр төлж сүүлийн гишгүүрт хүрэх нэгээс их зам байхгүй болно.
Input
Эхний мөрөнд гишгүүрийн тоо.
Дараагийн мөрөнд 1-р гишгүүрээс эхлэн сүүлийн гишгүүр хүртэлх гишгүүрээр дамжсаны төлбөрүүд зайгаар тусгаарлагдан өгөгдөнө.
Output
Эхний мөрөнд хамгийн бага төлбөр.
Хоёр дахь мөрөнд эхнээсээ сүүлийн гишгүүр хүртэл алхах гишгүүрийн дугаарууд зайгаар тусгаарлаж хэвлэнэ.
Example
Input:8 2 3 4 2 2 4 3 5Output:
14
2 4 6 8
Нэмсэн: | Bataa |
Огноо: | 2013-01-24 |
Хугацааны хязгаарлалт: | 1s |
Эх кодын хэмжээний хязгаарлалт: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Програмчлалын хэлүүд: | ADA95 ASM32 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE |
hide comments
|
|||||
2020-11-07 04:15:20
АЛГОРИТМЫН ЦАГААН ТОЛГОЙ PROFILE News Problems Status Ranking Forum ads via Carbon Limited time offer: Get 10 free Adobe Stock images. ADS VIA CARBON SPOJ time: 2020-11-07 04 : 06 : 06 Бодолт илгээх Миний бодолтууд Бүх бодолтууд Шилдэг бодолтууд PDF Жагсаалт руу буцах RGB7701 - Шинэ жилийн тээвэр Шугаман ертөнцийн шинэ жил болох гэж байна! Энэ ертөнцөд 1 × n хэмжээтэй хүснэгтийн нүднүүд шиг 1-ээс n хүртэлх бүхэл тоонуудаар дугаарлагдсан n ширхэг үүр байдаг. Энэ үүрнүүдэд хүмүүс амьдардаг. Гэхдээ үүрнээс гарах нь хүндрэлтэй учраас өөр үүрнүүд рүү очиход хэцүү байдаг байв. Хүмүүс бусад үүрэнд амьдардаг хүмүүстэй уулзахыг хүсэж байлаа. Тиймээс хэрэглэгч tncks0121 шинэ жилийн баяраар эдгээр үүрнүүдийн хооронд шилжих тээврийн систем хийжээ. Үүний тулд тэр эхлээд a1, a2 ..., an - 1 гэсэн n - 1 ширхэг эерэг бүхэл тоонуудыг тодорхойлов. 1 ≤ i ≤ n - 1 байх i бүхэл тоо бүрийн хувьд 1 ≤ ai ≤ n - i нөхцлийг хангана. Дараа нь тэр 1-ээс n - 1 хүртэлх бүхэл тоонуудаар дугаарлагдсан n - 1 ширхэг портал хийжээ. i-р (1 ≤ i ≤ n - 1) портал нь i болон (i + ai) үүрнүүдийг холбодог ба i-р порталыг ашиглан i-р үүрнээс (i + ai)-р үүрлүү л аялж чадна. Харамсалтай нь портаар буцаж явах боломжгүй юм, энэ нь i-р порталыг ашиглан (i + ai) р үүрнээс i-р үүр лүү шилжиж чадахгүй гэсэн үг. Портал ашиглан Шугаман ертөнцөөс гарч чадахгүй гэдгийг 1 ≤ ai ≤ n - i нөхцлөөс хялбархан харж болно. Одоо би 1-р үүрэнд зогсож байгаа ба t үүр лүү явахыг хүсэж байна. Гэхдээ би тэнд очиж болох эсэхийг мэдэхгүй байна. Уг тээврийн системийг ашиглан t үүр лүү явах боломжтой эсэхийг тодорхойлно уу. Input Эхний мөр нь зайгаар тусгаарлагдсан n (3 ≤ n ≤ 3 × 104) ба t (2 ≤ t ≤ n) бүхэл тоонуудыг агуулна. Эдгээр нь үүрнүүдийн тоо болон миний очихыг хүсэж байгаа үүрний дугаар юм. Хоёр дахь мөр нь зайгаар тусгаарлагдсан n - 1 ширхэг a1, a2, ..., an - 1 (1 ≤ ai ≤ n - i). бүхэл тоонуудыг агуулна. Өгөгдсөн тээврийн системийг ашиглан Шугаман ертөнцөөс гарч чадахгүй гэдэг нь баталгаатай байна. Output Хэрвээ би тээврийн системийг ашиглан t үүрлүү явж чадах бол "YES" гэж хэвлэнэ. Эсрэг тохиолдолд "NO" гэж хэвлэнэ. Example Оролт 1 : 8 4 1 2 1 2 1 2 1 Гаралт 1 : YES Оролт 2 : 8 5 1 2 1 2 1 1 1 Гаралт 2 : NO Тайлбар : Эхний жишээнд очсон үүрнүүд нь: 1, 2, 4; тиймээс бид 4-р үүрэнд амжилттай очиж чадна. Хоёр дахь жишээнд очиж болох боломжит үүрнүүд нь: 1, 2, 4, 6, 7, 8; тиймээс бид очихыг хүсэж буй 5-р үүр лүү очиж чадахгүй. Орчуулсан : Б.Даваабаяр Нэмсэн: Bataa Огноо: 2013-02-07 Хугацааны хязгаарлалт: 1s Эх кодын хэмжээний хязгаарлалт: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Програмчлалын хэлүүд: ADA95 ASM32 BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile ST TCL WHITESPACE Эх сурвалж: http://codeforces.com/problemset/problem/500/A Leave a Comment |Notes:| 1. Don't post any source code here.| 2. Please be careful, leave short comments only. Don't spam here.| 3. For more discussion (hints, ideas, solutions) please visit our forum.| 4. Authors are allowed to delete the post and use html code here (e.g. to provide some useful links).| About SPOJ RSS © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs. Feedback Not using Hotjar yet? Select an element on the page. |
|||||
2020-05-30 14:01:36
|
|||||
2020-05-30 14:00:20
l k ene hurtel huulah gej yvuulsan ym chini tuslay #include <iostream> using namespace std; int main() { int n , i , a[100]; long long dp[100] = {0} , b[100] , p[100]; cin >> n; for(i = 1 ; i <= n ; i++){ cin >> a[i]; } dp[0] = 0; dp[1] = a[1]; b[1] = 0; for(i = 2 ; i <= n ; i++){ if(dp[i - 1] < dp[i - 2]){ dp[i] = dp[i - 1] + a[i]; b[i] = i - 1; } else{ dp[i] = dp[i - 2] + a[i]; b[i] = i - 2; } } cout << dp[n] << '\n'; int k = 0; while(n != 0){ k++; p[k] = n; n = b[n]; } for(i = k ; i >= 1 ; i --)cout << p[i] << ' '; } |
|||||
2019-11-08 11:14:07
ez Last edit: 2019-11-08 11:14:19 |
|||||
2019-11-08 10:51:08
oof ur dick |
|||||
2019-11-06 12:13:27
ez bpdlogi |
|||||
2019-11-03 07:30:13
ooooooooooooooooooooooooooofffffffffffffffffffffffffffffffffffff |
|||||
2019-10-20 09:46:07
PO.TemPhozhing |
|||||
2019-08-11 12:28:22
amraa Last edit: 2019-08-11 12:29:14 |