样例和自己找的所有例子例子都过了,还是WA,求大神们解答!
谢谢!
#include<iostream>
#include<algorithm>
using namespace std;
int n1 = 0, n2 = 0;
int a1[505] = { 0 }, a2[505] = { 0 };
int ans[505][505] = { 0 };
int MAX = 0;
void print(int k, int cnt)
{
if (cnt == 1)
{
cout << a1[k];
if (cnt == MAX) cout << endl;
else cout << " ";
return;
}
for (int i = k - 1; i > 0; --i)
{
if (a1[k] > a1[i] && ans[k][n2] == 1 + ans[i][n2])
{
print(i, cnt - 1);
cout << a1[k];
if (cnt == MAX) cout << endl;
else cout << " ";
return;
}
}
}
int main()
{
cin >> n1;
for (int i = 1; i <= n1; ++i)
cin >> a1[i];
cin >> n2;
for (int i = 1; i <= n2; ++i)
cin >> a2[i];
for (int i = 1; i <= n1; ++i)
{
for (int j = 1; j <= n2; ++j)
{
if (a1[i] == a2[j])
{
ans[i][j] = 1;
for (int k = i - 1; k >= 1; --k)
{
if (a1[i] > a1[k] && ans[i][j] < ans[k][j] + 1)
ans[i][j] = ans[k][j] + 1;
}
MAX = max(MAX, ans[i][j]);
}
else ans[i][j] = ans[i][j - 1];
}
}
cout << MAX << endl;
if (MAX)
{
for (int i = n1; i > 0; --i)
{
if (MAX == ans[i][n2])
{
print(i, MAX);
break;
}
}
}
else cout << endl;
system("pause");
return 0;
}