cache[a][b] = A[a~(n-1)] 과 B[b~(m-1)]로 만들 수 있는 가장 긴 합친증가수열의 길이.
maxlength(int weight,int aa,int bb) = weight보다 큰 원소로 시작하는 cache[a][b]를 구한다.
A[a~(n-1)]과 B[b~(n-1)]중에서
weight보다 큰 원소를 찾고, 위치가 i인 원소를 찾으면
A안에 원소가 있을땐 max(A[i],i+1,b)을 호출하고 이값+1과 ret를 비교하여 큰 값을 ret에 저장.
B안에 원소가 있을땐 max(B[i],a,i+1)을 호출하고 이값+1과 ret를 비교하여 큰 값을 ret에 저장.
ret를 return 함.
이렇게 풀었습니다 ㅠㅠ 책에있는 풀이랑도 크게 차이점이 없어보이고.. 논리의 오류도 못찾겠는데.. 도와주세요!!
#include<iostream>#define MAX 101usingnamespacestd;inta[MAX],b[MAX];intcache[MAX][MAX];intn,m;intmaxlength(intweight,intaa,intbb){if(aa==n&&bb==m)return1;int&ret=cache[aa][bb];if(ret!=-1)returnret;inti,j;intmax=0;for(i=aa;i<n;i++){intk;if(weight<a[i])k=maxlength(a[i],i+1,bb);if(weight<a[i]&&max<k)max=k;}for(i=bb;i<m;i++){intk;if(weight<b[i])k=maxlength(b[i],aa,i+1);if(weight<b[i]&&max<k)max=k;}returnret=max+1;}intmain(){intT;for(cin>>T;T--;){inti,j;cin>>n>>m;for(i=0;i<n;i++)cin>>a[i];for(i=0;i<m;i++)cin>>b[i];for(i=0;i<=n;i++){for(j=0;j<=m;j++)cache[i][j]=-1;}intaaa=0;intbbb=0;for(i=0;i<n;i++)if(aaa<maxlength(a[i],i+1,0))aaa=maxlength(a[i],i+1,0);for(i=0;i<n;i++)if(bbb<maxlength(b[i],0,i+1))bbb=maxlength(b[i],0,i+1);if(aaa<bbb)printf("%d\n",bbb);elseprintf("%d\n",aaa);}return0;}
skan1543
JLIS
제가 푼 알고리즘은 이러합니다..
cache[a][b] = A[a~(n-1)] 과 B[b~(m-1)]로 만들 수 있는 가장 긴 합친증가수열의 길이.
maxlength(int weight,int aa,int bb) = weight보다 큰 원소로 시작하는 cache[a][b]를 구한다.
A[a~(n-1)]과 B[b~(n-1)]중에서
weight보다 큰 원소를 찾고, 위치가 i인 원소를 찾으면
A안에 원소가 있을땐 max(A[i],i+1,b)을 호출하고 이값+1과 ret를 비교하여 큰 값을 ret에 저장.
B안에 원소가 있을땐 max(B[i],a,i+1)을 호출하고 이값+1과 ret를 비교하여 큰 값을 ret에 저장.
ret를 return 함.
이렇게 풀었습니다 ㅠㅠ 책에있는 풀이랑도 크게 차이점이 없어보이고.. 논리의 오류도 못찾겠는데.. 도와주세요!!
10년 전