KLIS 오버플로우 질문! 시나브로 <a class="problem" href="/judge/problem/read/KLIS" title="K-th Longest Increasing Sequence">KLIS</a> 예제입력과 예제입력*2를 넣어본 결과, 성공해서 그냥 입력은 문제없는것 같아, 오버플로우가 문제인 것 같은데 어디가 문제인지 잘 모르겠습니다... 오버플로우가 아니라면 또 문제가 뭘까요?? // KLIS 20190217 // #알고리즘 #프로그래밍 #종만북 #난이도:상 #include <iostream> #include <cstring> #include <string> #include <vector> #include <algorithm> #include <cmath> #include <cstdio> using namespace std; template<typename T> void vectorclear(vector<T>& vec_obj) {vector<T> temp_obj; temp_obj.swap(vec_obj);} void stringclear(string& str) {string throwawaystr; str.swap(throwawaystr);} //기본셋 const long long BIGM = 2147483649; int n,k,putn,putseq; long long skip; vector<int> seq; vector<int> lis; vector<long long> countvec; vector<int> recon; int cashe[500]; long long cashecount[500]; int lengthlis(int index, const vector<int>& seq) { if(cashe[index]!=-1){return cashe[index];} //메모이제이션 if(index==(seq.size()-1)){return cashe[index]=1;} //기저 int ret=1; for(int i=1; i<seq.size()-index; i++) { if((seq[index]<seq[index+i])) {ret = max(ret,1+lengthlis(index+i,seq));} } return cashe[index]=ret; } long long count(int start) { if(lengthlis(start,seq)==1){return 1;} if(cashecount[start]!=-1){return cashecount[start];} long long ret=0; for(int next=start+1;next<n;next++) { if(((seq[start]<seq[next])&&(lengthlis(start,seq)==lengthlis(next,seq)+1))) { ret = min<long long>(BIGM,ret+count(next));} } return cashecount[start]=ret; } void reconst(int start) {if(start!=0){recon.push_back(seq[start]);} vector<pair<int,int>> sets; vectorclear(sets); for(int next=start+1;next<n;next++) {if((seq[start]<seq[next])&&(lengthlis(start,seq)==lengthlis(next,seq)+1)) {sets.push_back(make_pair(seq[next],next));}} sort(sets.begin(),sets.end()); for(int i=0;i<sets.size();i++) { int idx=sets[i].second; long long counts=count(idx); if(skip>=counts) {skip-=counts;} else {reconst(idx);break;} } } int main() { memset(cashe,-1,sizeof(cashe)); int C; cin>>C; while(C--) { vectorclear(seq); vectorclear(lis); vectorclear(countvec); vectorclear(recon); cin>>n>>k; skip=k-1; putn=n; seq.push_back(0); while(putn--) {cin>>putseq; seq.push_back(putseq);} n+=1; //for(int i=0;i<n;i++) //{memset(cashe,-1,sizeof(cashe)); //lis.push_back(lengthlis(i, seq));} memset(cashe,-1,sizeof(cashe)); memset(cashecount,-1,sizeof(cashecount)); for(int i=0;i<n;i++) {countvec.push_back(count(i));} //count까지 세팅 reconst(0); cout<<recon.size()<<endl; for(int i=0; i<recon.size(); i++) {cout<<recon[i]<<" ";} cout<<endl; } return 0; } 5년 전
0개의 댓글이 있습니다. 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
시나브로
예제입력과 예제입력*2를 넣어본 결과, 성공해서 그냥 입력은 문제없는것 같아,
오버플로우가 문제인 것 같은데 어디가 문제인지 잘 모르겠습니다...
오버플로우가 아니라면 또 문제가 뭘까요??
5년 전