[폭력 DP][폭력 STL] 스노우 2017 & LOJ#2256.영웅 연맹
j는 매우 크고 1018이 있지만 j는 2, 3, 5, 7 세 가지 질수밖에 없기 때문에 j가 얻을 수 있는 값 상한선은 (logm)4이고 이 상한선보다 훨씬 작다.게으르기 때문에 더 이상 최적화하지 않겠습니다. DP 그룹은 맵으로 직접 저장하고 이동할 때 한 번씩 훑어봅니다.
그런데 이곳에서 10여 초를 뛰고 O2를 켜서 3초를 뛰고 T를 건네주고 마지막 점을 찍었는데...
맵이 안 되면 unordered맵, 억지로 0.5s 들어가기...
#include
",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&k[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
f[0]=0; ans=1LL<<60;
for(int i=1;i<=n;i++){
for(auto v : f){
if(v.fi==0){
for(int j=1;j<=k[i];j++)
if(g.count(j)) fix(g[j],j*c[i]);
else g[j]=j*c[i];
g[0]=0;
continue;
}
if(g.count(v.fi)) fix(g[v.fi],v.se);
else g[v.fi]=v.se;
for(int j=2;j<=k[i];j++){
if(v.fi*j>=m){
fix(ans,v.se+j*c[i]);
break;
}
if(v.se+j*c[i]>=ans) break;
if(g.count(v.fi*j)) fix(g[v.fi*j],v.se+c[i]*j);
else g[v.fi*j]=v.se+c[i]*j;
}
}
swap(f,g); g.clear();
}
printf("%lld
",ans);
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
zoj3966 Domino Tiling dp제목 대의: n*m의 바둑판을 주면 1x2의 칸으로만 조립할 수 있고 4개의 다른 칸의 뿔이 동시에 한 곳에 모일 수 없다.200조 정도의 입력과 출력 임의의 방안. 문제풀이: 제한 조건이 너무 강하기 때문에 가장 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
