Beküldés #24 429

2026-02-11 14:59:00

cpp17

Elfogadva 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];			
}

	Összpont	Teszt	Verdikt		Idő	Memória
base	35/35
		1	Elfogadva	0/0	1ms	508 KiB
		2	Elfogadva	0/0	25ms	1080 KiB
		3	Elfogadva	1/1	1ms	316 KiB
		4	Elfogadva	1/1	1ms	316 KiB
		5	Elfogadva	1/1	1ms	316 KiB
		6	Elfogadva	1/1	1ms	316 KiB
		7	Elfogadva	1/1	1ms	500 KiB
		8	Elfogadva	2/2	1ms	316 KiB
		9	Elfogadva	2/2	1ms	412 KiB
		10	Elfogadva	2/2	2ms	424 KiB
		11	Elfogadva	2/2	2ms	432 KiB
		12	Elfogadva	2/2	2ms	316 KiB
		13	Elfogadva	2/2	3ms	316 KiB
		14	Elfogadva	2/2	4ms	316 KiB
		15	Elfogadva	2/2	8ms	632 KiB
		16	Elfogadva	2/2	13ms	800 KiB
		17	Elfogadva	2/2	17ms	820 KiB
		18	Elfogadva	2/2	19ms	1044 KiB
		19	Elfogadva	2/2	21ms	1076 KiB
		20	Elfogadva	2/2	21ms	1076 KiB
		21	Elfogadva	2/2	24ms	1076 KiB
		22	Elfogadva	2/2	24ms	1268 KiB