예제 입력이 잘 나오는 것으로 보아 overflow 문제인 거 같은데 도저히 감을 못잡겠습니다.. 문제 조건에 따라 MAX값 보다 signed 32-bit integer의 MAX값보다 높게 설정했고.. lis와 count는 책을 참고하여 작성했구요, KLIS를 구하는 함수는 저만의 방식으로 작성해보았습니다. 남의 code를 보고 문제를 찾는 것이 쉽지 않다는 것은 알지만 혹시 도움을 주실 수 있는 분이 있다면 간곡히 부탁드립니다. 감사합니다.
#include <iostream>#include <algorithm>#include <vector>usingnamespacestd;constlonglongMAX=2500000000;intn;longlongk;intlisCache[501],S[500],pos[100000+1];longlongcountCache[501],countLIS[100000+1];vector<int>KLIS;// S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.intlis(intstart){int&ret=lisCache[start+1];if(ret!=-1)returnret;// lis의 최소 길이는 1.ret=1;for(intnext=start+1;next<n;++next){if(start==-1||S[start]<S[next])ret=max(ret,lis(next)+1);}returnret;}// S[start]에서 시작하는 LIS의 수를 반환.longlongcount(intstart){// base case : LIS의 길이가 1인 경우.if(lis(start)==1)return1;// memoizationlonglong&ret=countCache[start+1];if(ret!=-1)returnret;ret=0;for(intnext=start+1;next<n;++next){if((start==-1||S[start]<S[next])&&lis(start)==lis(next)+1)ret=min<longlong>(MAX,ret+count(next));}returnret;}voidklis(intstart,intlis_0){intlength=lis(start)-1;fill(&countLIS[0],&countLIS[0]+100000+1,0);for(inti=start+1;i<n;++i){if((start==-1||S[start]<S[i])&&lis(i)==length){countLIS[S[i]]=count(i);}}intnewStart=start+1;for(inti=1;i<100001;++i){if(k<=countLIS[i]){KLIS.push_back(i);newStart=pos[i];break;}k-=countLIS[i];}if(KLIS.size()==lis_0)return;klis(newStart,lis_0);}intmain(){intT;cin>>T;for(inti=0;i<T;++i){cin>>n>>k;for(intj=0;j<n;++j){cin>>S[j];pos[S[j]]=j;}fill(&lisCache[0],&lisCache[0]+501,-1);fill(&countCache[0],&countCache[0]+501,-1);intlis_0=lis(0);cout<<lis_0<<endl;klis(-1,lis_0);for(intj=0;j<KLIS.size()-1;++j){cout<<KLIS[j]<<" ";}cout<<KLIS[KLIS.size()-1]<<endl;KLIS.clear();}}
4년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
TLB_MISS
예제 입력이 잘 나오는 것으로 보아 overflow 문제인 거 같은데 도저히 감을 못잡겠습니다.. 문제 조건에 따라 MAX값 보다 signed 32-bit integer의 MAX값보다 높게 설정했고.. lis와 count는 책을 참고하여 작성했구요, KLIS를 구하는 함수는 저만의 방식으로 작성해보았습니다. 남의 code를 보고 문제를 찾는 것이 쉽지 않다는 것은 알지만 혹시 도움을 주실 수 있는 분이 있다면 간곡히 부탁드립니다. 감사합니다.
4년 전