ANOTHER STUPID MISTAKE!!!!!!!!
MINE WOULD ACC before if i maintained THE CORRECT OUTPUT FORMAT(print case number)
these days i amm so careless
![:P](./images/smilies/icon_razz.gif)
![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
thank UUUUUUUUUUUU
keep posting!!!!!!
Moderator: Board moderators
Code: Select all
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
int a[255], b[255];
int c[255][255];
int main() {
int T, idx = 0;
scanf("%d", &T);
while (T--) {
int n, p, q;
scanf("%d%d%d", &n, &p, &q);
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for (int i = 0; i <= p; i++) scanf("%d", &a[i]);
for (int i = 0; i <= q; i++) scanf("%d", &b[i]);
memset(c, 0, sizeof(c));
for (int i = 1; i <= p + 1; i++) {
for (int j = 1; j <= q + 1; j++) {
if (a[i - 1] == b[j - 1]) {
c[i][j] = c[i - 1][j - 1] + 1;
}
else c[i][j] = max(c[i - 1][j], c[i][j - 1]);
}
}
printf("Case %d: %d\n", ++idx, c[p + 1][q + 1]);
}
return 0;
}
Code: Select all
1
3 4 5
1 7 6 5 9
1 8 7 6 5 9
Code: Select all
4
Code: Select all
3
mf wrote:My accepted program replaces each number of the 2nd sequence with its index in the 1st sequence, and finds the length of LIS of the resulting sequence.
Code: Select all
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int arr1[100000],arr2[100000];
vector<int> v,v1,v2;
int t;
cin>>t;
for (int i=0;i<t;i++)
{
int n,a,b,temp;
cin>>n>>a>>b;
v.clear();
v1.clear();
v2.clear();
a++;b++;
memset(arr1,0,sizeof(arr1));
memset(arr2,0,sizeof(arr2));
for (int j=1;j<=a;j++)
{
cin>>temp;
arr1[temp]=j;
v2.push_back(temp);
}
int pj=0;
for (int j=1;j<=b;j++)
{
cin>>temp;
if (arr1[temp]!=0)
{
pj++;
arr2[pj]=arr1[temp];
v.push_back(temp);
arr1[temp]=-1;
}
}
for (int j=0;j<v2.size();j++)
if (arr1[v2[j]]==-1)
v1.push_back(v2[j]);
int dp[v.size()+1][v1.size()+1];
memset(dp,0,sizeof(dp));
for (int j=1;j<=v.size();j++)
for (int k=1;k<=v1.size();k++)
{
if (v[j-1]==v1[k-1])
dp[j][k]=dp[j-1][k-1]+1;
else if (dp[j-1][k] > dp[j][k-1])
dp[j][k]=dp[j-1][k];
else
dp[j][k]=dp[j][k-1];
}
cout<<"Case "<<i+1<<": "<<dp[v.size()][v1.size()]<<endl;
}
//system("pause");
return 0;
}