286912026-05-27 18:03:46KristófDombokcpp17Elfogadva 100/100342ms294344 KiB
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll=long long;
ll INF=1e15;

struct Node
{
ll cost=INF;
ll lastremoval,cval;
};

ll costf(ll left,ll right,ll mid)
{
return max(0LL,left-(mid-1))+max(0LL,right-(mid-1));
}

int main() {
	int n,k;
	cin>>n;
	vector<int> height(n+2,0);
	for(int i=1;i<=n;i++)cin>>height[i];
	k=(n+1)/2;
	vector<vector<Node>> dp(k+1,vector<Node> (n+1));
	for(int i=1;i<=k;i++)
		{
		for(int j=1;j<=n;j++)
			{
			if((j+1)/2<i)continue;
			if(i==1)
				{
				ll cost=costf(height[j-1],height[j+1],height[j]);
				if(cost<=dp[i][j-1].cost)
					{
					dp[i][j].cost=cost;
					dp[i][j].lastremoval=j+1;
					dp[i][j].cval=height[j+1]-max(0,height[j+1]-(height[j]-1));
					}
				else dp[i][j]=dp[i][j-1];
				}
			else
				{
				int leftp=dp[i-1][j-2].lastremoval;
				ll cost;
				if(leftp==j-1)
					{
					cost=costf(dp[i-1][j-2].cval,height[j+1],height[j]);
					}
				else cost=costf(height[j-1],height[j+1],height[j]);
				if(cost+dp[i-1][j-2].cost<=dp[i][j-1].cost)
					{
					dp[i][j].cost=cost+dp[i-1][j-2].cost;
					dp[i][j].lastremoval=j+1;
					dp[i][j].cval=height[j+1]-max(0,height[j+1]-(height[j]-1));
					}
				else dp[i][j]=dp[i][j-1];
				}
			}
		}
	for(int i=1;i<=k;i++)
		{
			cout<<dp[i][n].cost<<" ";
		}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
00/0
1Elfogadva1ms508 KiB
2Elfogadva1ms316 KiB
3Elfogadva1ms316 KiB
17/7
4Elfogadva1ms508 KiB
5Elfogadva1ms332 KiB
6Elfogadva2ms316 KiB
7Elfogadva1ms316 KiB
8Elfogadva2ms316 KiB
9Elfogadva3ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms500 KiB
12Elfogadva2ms316 KiB
13Elfogadva1ms316 KiB
215/15
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms388 KiB
19Elfogadva1ms316 KiB
20Elfogadva2ms316 KiB
21Elfogadva1ms316 KiB
22Elfogadva1ms316 KiB
23Elfogadva1ms316 KiB
24Elfogadva1ms316 KiB
25Elfogadva1ms316 KiB
26Elfogadva1ms316 KiB
27Elfogadva1ms316 KiB
28Elfogadva1ms316 KiB
313/13
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva1ms544 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva2ms580 KiB
39Elfogadva1ms316 KiB
40Elfogadva1ms316 KiB
418/18
41Elfogadva3ms316 KiB
42Elfogadva3ms316 KiB
43Elfogadva3ms316 KiB
44Elfogadva3ms316 KiB
45Elfogadva1ms316 KiB
46Elfogadva1ms316 KiB
47Elfogadva1ms320 KiB
48Elfogadva1ms316 KiB
49Elfogadva1ms316 KiB
522/22
50Elfogadva1ms328 KiB
51Elfogadva1ms316 KiB
52Elfogadva4ms3124 KiB
53Elfogadva4ms3128 KiB
54Elfogadva4ms3136 KiB
55Elfogadva4ms3136 KiB
56Elfogadva4ms3160 KiB
57Elfogadva4ms3136 KiB
58Elfogadva4ms3136 KiB
59Elfogadva4ms3200 KiB
60Elfogadva4ms3136 KiB
61Elfogadva4ms3136 KiB
62Elfogadva4ms3124 KiB
63Elfogadva4ms3124 KiB
625/25
64Elfogadva16ms12096 KiB
65Elfogadva16ms12232 KiB
66Elfogadva282ms294340 KiB
67Elfogadva342ms294200 KiB
68Elfogadva337ms294140 KiB
69Elfogadva280ms294320 KiB
70Elfogadva275ms294244 KiB
71Elfogadva287ms294344 KiB
72Elfogadva284ms294204 KiB
73Elfogadva326ms294204 KiB
74Elfogadva280ms294268 KiB
75Elfogadva284ms294312 KiB
76Elfogadva331ms294208 KiB