Submission #940247

#TimeUsernameProblemLanguageResultExecution timeMemory
940247Angus_YeungGroup Photo (JOI21_ho_t3)C++14
0 / 100
1 ms344 KiB
#include <bits/stdc++.h> #define len first #define node second #define pii pair<ll, ll> typedef long long ll; const ll MOD = 1000000007LL; const ll INF = 1e15; using namespace std; ll n, a[5010], dp[5010], pos[5010], tmp; vector<ll> p[5010]; ll f(ll id, ll l, ll r) { if (l > r) return 0; return upper_bound(p[id].begin(), p[id].end(), r)-lower_bound(p[id].begin(), p[id].end(), l); } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; pos[a[i]] = i; for (int j = 1; j < i; j++) p[i].push_back(a[j]); sort(p[i].begin(), p[i].end()); } dp[0] = 0; for (int i = 1; i <= n; i++) { dp[i] = INF; for (int j = 1; j <= i; j++) { tmp = 0; for (int k = j; k <= i; k++) { tmp += f(pos[i+j-k], i+1, n); tmp += f(pos[i+j-k], j, k-1); } dp[i] = min(dp[i], dp[j-1]+tmp); // cout << dp[j-1]+tmp << ' '; } // cout << "\n"; } cout << dp[n]-1 << "\n"; return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...