| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 574581 | 2022-06-08T21:35:00 Z | beaboss | Rabbit Carrot (LMIO19_triusis) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
ll mod = 1000000007;
typedef long long ll;
int main() {
ll n, m;
cin >> n >> m;
vector<ll> vals(n);
for (ll i = 0; i < n; i++) {
cin >> vals[i];
}
vector<ll> dp(n + 1, 0);
for (ll i = 0; i < n; i++) {
if (m * (i + 1) < vals[i]) continue;
ll best = -1;
ll best_s = 0;
for (ll j = 0; j < i; j++) {
if (vals[i] > vals[j] + m * (i - j)) continue;
if (dp[j + 1] >= best_s) {
best_s = dp[j + 1];
best = j;
}
}
dp[i + 1] = 1 + dp[best + 1];
}
cout << n - dp[n] << endl;
}