E. By Elevator or Stairs?.Codeforces Round #595 (Div. 3)
전언
하나 말하자면, 이것은 내가 해 본 것 중 가장 간단한 E문제이다
제목의 뜻
빌딩이 있다고 말하고 1층에서 1층까지의 가장 짧은 시간을 구해 달라고 하세요.그 중에서 위층에는 두 가지 방식이 있다.계단을 걷다엘리베이터를 타다.계단은 바로 갈 수 있고 엘리베이터는 대기 시간이 필요하다.데이터는 층과 층 사이의 대기 시간을 계산하지 않는 두 가지 방식으로 위층에 올라가는 데 필요한 시간을 제공한다.
방법
dp를 생각하기 쉽고 가장 기초적인 dp(div3도 감히 이렇게 알고리즘 문제를 낼 수 있을 것 같다)
상태 dp[i][0]는 계단을 올라가는 데 필요한 가장 짧은 시간을 나타낸다.dp[i][1]은 엘리베이터를 탈 때 i층으로 올라가는 데 걸리는 가장 짧은 시간을 나타낸다.
전이 방정식
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+a[i-1][0]; dp[i][1]=min(dp[i-1][0]+a[i-1][1]+m,dp[i-1][1]+a[i-1][1]);
코드 #include
using namespace std;
int n,m;
int a[200005][2];
int dp[200005][2];
int main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
cin>>a[i][0];
}
for(int i=1;i<=n-1;i++){
cin>>a[i][1];
}
dp[2][0]=a[1][0];
dp[2][1]=a[1][1]+m;
for(int i=3;i<=n;i++){
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+a[i-1][0];
dp[i][1]=min(dp[i-1][0]+a[i-1][1]+m,dp[i-1][1]+a[i-1][1]);
}
for(int i=1;i<=n;i++){
cout<0],dp[i][1])<<" ";
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
빌딩이 있다고 말하고 1층에서 1층까지의 가장 짧은 시간을 구해 달라고 하세요.그 중에서 위층에는 두 가지 방식이 있다.계단을 걷다엘리베이터를 타다.계단은 바로 갈 수 있고 엘리베이터는 대기 시간이 필요하다.데이터는 층과 층 사이의 대기 시간을 계산하지 않는 두 가지 방식으로 위층에 올라가는 데 필요한 시간을 제공한다.
방법
dp를 생각하기 쉽고 가장 기초적인 dp(div3도 감히 이렇게 알고리즘 문제를 낼 수 있을 것 같다)
상태 dp[i][0]는 계단을 올라가는 데 필요한 가장 짧은 시간을 나타낸다.dp[i][1]은 엘리베이터를 탈 때 i층으로 올라가는 데 걸리는 가장 짧은 시간을 나타낸다.
전이 방정식
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+a[i-1][0]; dp[i][1]=min(dp[i-1][0]+a[i-1][1]+m,dp[i-1][1]+a[i-1][1]);
코드 #include
using namespace std;
int n,m;
int a[200005][2];
int dp[200005][2];
int main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
cin>>a[i][0];
}
for(int i=1;i<=n-1;i++){
cin>>a[i][1];
}
dp[2][0]=a[1][0];
dp[2][1]=a[1][1]+m;
for(int i=3;i<=n;i++){
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+a[i-1][0];
dp[i][1]=min(dp[i-1][0]+a[i-1][1]+m,dp[i-1][1]+a[i-1][1]);
}
for(int i=1;i<=n;i++){
cout<0],dp[i][1])<<" ";
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+a[i-1][0]; dp[i][1]=min(dp[i-1][0]+a[i-1][1]+m,dp[i-1][1]+a[i-1][1]);
코드 #include
using namespace std;
int n,m;
int a[200005][2];
int dp[200005][2];
int main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
cin>>a[i][0];
}
for(int i=1;i<=n-1;i++){
cin>>a[i][1];
}
dp[2][0]=a[1][0];
dp[2][1]=a[1][1]+m;
for(int i=3;i<=n;i++){
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+a[i-1][0];
dp[i][1]=min(dp[i-1][0]+a[i-1][1]+m,dp[i-1][1]+a[i-1][1]);
}
for(int i=1;i<=n;i++){
cout<0],dp[i][1])<<" ";
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
using namespace std;
int n,m;
int a[200005][2];
int dp[200005][2];
int main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
cin>>a[i][0];
}
for(int i=1;i<=n-1;i++){
cin>>a[i][1];
}
dp[2][0]=a[1][0];
dp[2][1]=a[1][1]+m;
for(int i=3;i<=n;i++){
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+a[i-1][0];
dp[i][1]=min(dp[i-1][0]+a[i-1][1]+m,dp[i-1][1]+a[i-1][1]);
}
for(int i=1;i<=n;i++){
cout<0],dp[i][1])<<" ";
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
