Hello, I was trying to solve UVa 103 using O(N2) Longest Increasing Subsequence. Here is my code:
#include <bits/stdc++.h>
using namespace std;
int K, N, dp[31];
pair<vector<int>, int> A[31];
string hist[31];
bool canFit(int i, int j) {
for (int k = 0; k < N; ++k)
if (A[i].first[k] >= A[j].first[k])
return false;
return true;
}
int main() {
while (cin >> K >> N) {
for (int i = 0; i < K; ++i) {
A[i].first.resize(N, 0);
for (int j = 0; j < N; ++j)
cin >> A[i].first[j];
A[i].second = i;
sort(A[i].first.begin(), A[i].first.end());
}
sort(A, A+K);
fill_n(dp, 31, 1);
for (int i = 0; i < K; ++i)
hist[i] = to_string(A[i].second+1);
int ans = 1;
string best = "1";
for (int i = 1; i < K; ++i)
for (int j = 0; j < i; ++j)
if (canFit(j, i) && dp[j]+1 > dp[i]) {
dp[i] = dp[j]+1;
hist[i] = hist[j] + ' ' + to_string(A[i].second+1);
if (dp[i] > ans) {
ans = dp[i];
best = hist[i];
}
}
cout << ans << '\n' << best << '\n';
}
return 0;
}
I got WA with this submission. However, if I change one small detail, the code gets AC:
hist[i] = hist[j] + ' ' + to_string(A[i].second+1);
// Make this >= instead of >
// i.e. I save a maximum length path even if I already have one
if (dp[i] >= ans) {
ans = dp[i];
best = hist[i];
}
Why is this? I thought that using the strict >
was okay, since the problem says that "If there is more than one longest nesting string then any one of them can be output." Is there something I'm missing? Thanks.