CDOJ 1638 Easy Problem
한 2 차원 배열 로 어떤 계단 입구 에 도착 하 는 데 걸 린 시간 을 표시 한 다음 에 아래층 에서 고 층 DP 로 가면 된다.왼쪽 계단 마다 더 높 은 층 으로 올 라 가면 모든 물건 을 보 내 고 왼쪽으로 돌아 가 거나 오른쪽으로 바로 갈 수 있 습 니 다.
#include
int dp[101][2];
char floo[101];
int end[101][2];
int main()
{
int T, n, m, top, tmp;
scanf("%d", &T);
for(int cases=1; cases<=T; ++cases)
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i)
{
scanf("%s", floo);
end[i][0] = m-1;
end[i][1] = 0;
for(int j=1; j end[i][1])
end[i][1] = j;
if(j < end[i][0])
end[i][0] = j;
}
}
}
if(m < 3)
{
printf("Case #%d: %d
", cases, n-1);
continue;
}
for(top = n; top>=1; --top)
{
if(end[top][0] == m-1)
continue;
else break;
}
if(top == 0)
{
printf("Case #%d: %d
", cases, n-1);
continue;
}
dp[0][0] = dp[0][1] = -1;
for(int i=1; i<=top; ++i)
{
dp[i][0] = dp[i][1] = 0x0fffffff;
if(end[i][0] != m-1)
{
tmp = dp[i-1][0]+1+2*end[i][1];
if(tmp < dp[i][0])
dp[i][0] = tmp;
tmp = dp[i-1][0]+m;
if(tmp < dp[i][1])
dp[i][1] = tmp;
tmp = dp[i-1][1]+1+2*(m-1-end[i][0]);
if(tmp < dp[i][1])
dp[i][1] = tmp;
tmp = dp[i-1][1]+m;
if(tmp < dp[i][0])
dp[i][0] = tmp;
}
else
{
tmp = dp[i-1][0]+1;
if(tmp < dp[i][0])
dp[i][0] = tmp;
tmp = dp[i-1][0]+m;
if(tmp < dp[i][1])
dp[i][1] = tmp;
tmp = dp[i-1][1]+1;
if(tmp < dp[i][1])
dp[i][1] = tmp;
tmp = dp[i-1][1]+m;
if(tmp < dp[i][0])
dp[i][0] = tmp;
}
}
int ans = (dp[top][0]
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 10844번 쉬운 계단 수 - node.js문제 설명 계단수: 인접한 모든 자리의 차이가 1인 수 (EX. 로직 설명 N = 2일 때 가능한 계단수를 생각해보자. 해당 숫자들을 보면 십의자리 숫자들은 일의자리 숫자가 무엇이 오는지에 따라 올 수 있는 단어들이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.