287652026-05-28 22:04:57LazurAndrasDombokcpp17Elfogadva 100/100360ms314676 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5005, INF = 1e9;

int dp[N][N][3];

int mn(int a, int b, int c)
{
    return min(min(a, b), c);
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
	int n; cin >> n;
    int m = (n+1) / 2;
    vector<int>a(n+1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    a[0] = -INF;
    a.push_back(-INF);
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k < 3; k++)
                dp[i][j][k] = INF;
    for(int i = 0; i <= n; i++) dp[i][0][0] = 0;
    dp[1][1][2] = max(0LL, a[0]+1 - a[1]) + max(0LL, a[2]+1 - a[1]);
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1]);
            dp[i][j][1] = dp[i-1][j][2];
            dp[i][j][2] = max(0LL, a[i+1]+1 - a[i]);
            dp[i][j][2] += min(dp[i-1][j-1][0] + max(0LL, a[i-1]+1 - a[i]), dp[i-1][j-1][1] + max(0LL, min(a[i-2], a[i-1]+1) - a[i]));
        }
    }
    for(int j = 1; j <= m; j++) cout << mn(dp[n][j][0], dp[n][j][1], dp[n][j][2]) << " ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
00/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
3Elfogadva1ms316 KiB
17/7
4Elfogadva1ms500 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms508 KiB
7Elfogadva1ms316 KiB
8Elfogadva1ms508 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva2ms316 KiB
13Elfogadva2ms316 KiB
215/15
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms456 KiB
18Elfogadva1ms548 KiB
19Elfogadva1ms316 KiB
20Elfogadva3ms508 KiB
21Elfogadva2ms316 KiB
22Elfogadva1ms500 KiB
23Elfogadva1ms316 KiB
24Elfogadva2ms316 KiB
25Elfogadva1ms316 KiB
26Elfogadva1ms316 KiB
27Elfogadva1ms500 KiB
28Elfogadva1ms316 KiB
313/13
29Elfogadva1ms564 KiB
30Elfogadva2ms920 KiB
31Elfogadva2ms820 KiB
32Elfogadva2ms840 KiB
33Elfogadva1ms820 KiB
34Elfogadva2ms820 KiB
35Elfogadva1ms820 KiB
36Elfogadva1ms820 KiB
37Elfogadva1ms824 KiB
38Elfogadva1ms820 KiB
39Elfogadva3ms900 KiB
40Elfogadva2ms820 KiB
418/18
41Elfogadva2ms820 KiB
42Elfogadva2ms1012 KiB
43Elfogadva2ms1040 KiB
44Elfogadva2ms820 KiB
45Elfogadva1ms564 KiB
46Elfogadva1ms564 KiB
47Elfogadva1ms948 KiB
48Elfogadva2ms820 KiB
49Elfogadva1ms820 KiB
522/22
50Elfogadva1ms820 KiB
51Elfogadva2ms820 KiB
52Elfogadva4ms5468 KiB
53Elfogadva6ms5416 KiB
54Elfogadva6ms5468 KiB
55Elfogadva4ms5336 KiB
56Elfogadva4ms5516 KiB
57Elfogadva6ms5504 KiB
58Elfogadva4ms5444 KiB
59Elfogadva4ms5428 KiB
60Elfogadva4ms5368 KiB
61Elfogadva6ms5504 KiB
62Elfogadva6ms5428 KiB
63Elfogadva4ms5304 KiB
625/25
64Elfogadva17ms16376 KiB
65Elfogadva17ms16436 KiB
66Elfogadva291ms314620 KiB
67Elfogadva293ms314576 KiB
68Elfogadva360ms314676 KiB
69Elfogadva356ms314668 KiB
70Elfogadva287ms314676 KiB
71Elfogadva291ms314668 KiB
72Elfogadva356ms314676 KiB
73Elfogadva356ms314676 KiB
74Elfogadva289ms314672 KiB
75Elfogadva287ms314668 KiB
76Elfogadva342ms314676 KiB