//naive solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<int> a (n+1, 0);
for(int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] -= m*i;
}
//find the longest nonincreasing subsequence starting with 0
int ans = 0;
vector<int> dp(n+1, 0);
dp[0] = 1;
for(int i = 0; i < a.size(); ++i) {
for(int j = 0; j < i; ++j) {
if(dp[j] == 0) continue;
if(a[j] >= a[i]) {dp[i] = max(dp[i], dp[j]+1);}
}
ans = max(ans, dp[i]);
}
cout << n+1-ans;
//cout << endl << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |