Submission #24,429

2026-02-11 14:59:00

cpp17

Accepted 35/35

25ms

1268 KiB

// UUID: 3927f242-544b-4a51-9b2a-d78149f6bed2
#include <bits/stdc++.h>
using namespace std;

/*
6
3 5  9  7  1  6
3 8 12 15 13 19

5 2  6  3  3  1  9  2  2  4  1  1  7  6  5
5 7 11 10 13 11 20 13 15 17 16 17 23 23 28  
Dinamikus Programozás
DP

dp[i]: az i. szigetre eljutás minimális összköltsége
dp[1] = dij[1]
dp[2] = dij[1]+dij[2]
i = 3..n:
dp[i] = min(dp[i-1], dp[i-2]) + dij[i]
*/

int main() {
	int n;
	cin>>n;
	vector<int>v(n);
	vector<int>dp(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	dp[0]=v[0];
	dp[1]=v[0]+v[1];
	for(int i=2;i<n;i++){
	dp[i]=v[i]+min(dp[i-1],dp[i-2]);
	}
	cout<<dp[n-1];			
}

	Sum	Test	Verdict		Time	Memory
base	35/35
		1	Accepted	0/0	1ms	508 KiB
		2	Accepted	0/0	25ms	1080 KiB
		3	Accepted	1/1	1ms	316 KiB
		4	Accepted	1/1	1ms	316 KiB
		5	Accepted	1/1	1ms	316 KiB
		6	Accepted	1/1	1ms	316 KiB
		7	Accepted	1/1	1ms	500 KiB
		8	Accepted	2/2	1ms	316 KiB
		9	Accepted	2/2	1ms	412 KiB
		10	Accepted	2/2	2ms	424 KiB
		11	Accepted	2/2	2ms	432 KiB
		12	Accepted	2/2	2ms	316 KiB
		13	Accepted	2/2	3ms	316 KiB
		14	Accepted	2/2	4ms	316 KiB
		15	Accepted	2/2	8ms	632 KiB
		16	Accepted	2/2	13ms	800 KiB
		17	Accepted	2/2	17ms	820 KiB
		18	Accepted	2/2	19ms	1044 KiB
		19	Accepted	2/2	21ms	1076 KiB
		20	Accepted	2/2	21ms	1076 KiB
		21	Accepted	2/2	24ms	1076 KiB
		22	Accepted	2/2	24ms	1268 KiB