Gym - 100451B - 대용량 + DP
문제 해결 방법:
원래의 한노타 이동 공식은 (2^n)-1이다. 그러면 우리가 두 개의 크기를 똑같이 보면 한 개의 이동비가 2로 변하는 것과 같다. 두 개의 상하 순서를 고려하지 않고 이동 횟수는 2*((2^n)-1)=2^(n+1)-2
현재의 문제는 같은 크기의 두 개의 최종 순서를 고려해야 한다는 것이다.
g[i]로 이동 전 2*i 블록의 최소 걸음수를 표시하고 r[i]로 이동 전 2*I 블록을 표시하지만 마지막 두 블록의 순서는 요구와 전도된 최소 걸음수이다.
원래 i층이 12모드인 것을 알았다면 21모드가 되려면 g[i]=r[i-1]+2+(2^i)-2, r[i-1]는 앞의 2*(i-1)층을 옮겼다는 뜻이고, 2는
12가 21이 되는 데 필요한 걸음수. 두 개의 바인딩을 다른 막대기로 바로 옮기면 된다. 뒤에 앞의 2*(i-1)층이 다시 i층 위로 이동하는 걸음수이다. i-1층은 한 번만 더 옮기기 때문에 필요할 때 뒤바뀌고 앞의 걸음수는 짝수이기 때문에 원래와 같다.
r[i]= g[i-1]+4+2^(i+1)-4, 거꾸로 된 이상 12가 마지막인지 12인지는 12가 두 번 움직이는 것으로 볼 수 있고, 앞 2*(i-1)층도 두 번 움직이기 때문에 이번에는 g[i-1]만 움직이면 되니까 2^(i+1)-4는 2*(i-1)층이 두 번 옮기는 걸음, 4는 12가 두 번 옮기는 걸음이다.
큰 숫자가 없으면 간단하다.
#include
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int mx = 2e3 + 10;
int a[mx],n,p[mx];
int g[mx],r[mx];
int main()
{
scanf("%d",&n);
p[0] = 1;
for(int i=1;ia[1]) g[1] = 3,r[1] = 2;
else g[1] = 2,r[1] = 3;
for(int i=2;i<=n;i++){
if(a[i*2]>a[2*i-1]){
g[i] = g[i-1] + p[i+1];
r[i] = r[i-1] + p[i];
}else{
g[i] = r[i-1] + p[i];
r[i] = g[i-1] + p[i+1];
}
}
printf("%d
",g[n]);
return 0;
} 큰 숫자 추가:
#include
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int mx = 2e3 + 10;
int a[2*mx],n,p[mx][mx],siz[mx];
int g[mx],r[mx],sizg,sizr;
int add(int *r,int *t,int cnt2)
{
int c = 0,i = 0;
while(ia[1]) g[0] = 3,r[0] = 2;
else g[0] = 2,r[0] = 3;
int *x = g,*y = r;
for(int i=2;i<=n;i++){
if(a[i*2]>a[2*i-1]){
//g[i] = g[i-1] + p[i+1];
sizg = add(x,p[i+1],siz[i+1]);
sizr = add(y,p[i],siz[i]);
//r[i] = r[i-1] + p[i];
}else{
swap(x,y);
//g[i] = r[i-1] + p[i];
sizg = add(x,p[i],siz[i]);
sizr = add(y,p[i+1],siz[i+1]);
//r[i] = g[i-1] + p[i+1];
}
}
printf("%d",x[sizg-1]);
for(int i=sizg-2;i>=0;i--) printf("%04d",x[i]);
puts("");
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
