|
|
back to boardO(k^2) dp solution Posted by lnxdx 4 Aug 2019 00:22 // ITNOA // O(k^2) dp by lnxdx, Mashhad, 2019 #include<bits/stdc++.h> using namespace std; const int N = 110; pair<int, int>a[N]; int dp[N]; int main() { int n, m, k; cin >> n >> m >> k; for (int i = 0;i < k;i++) cin >> a[i].first >> a[i].second; sort(a, a + k); int lis = 0; for (int i = 0;i < k;i++) { dp[i] = 1; for (int j = 0;j < i && a[j].first < a[i].first;j++) if (a[j].second < a[i].second) dp[i] = max(dp[i], dp[j] + 1); lis = max(lis, dp[i]); } double ans = 100 * ((m - lis) + (n - lis) + sqrt(2)*lis); cout << round(ans); } |
|
|