9도 OJ 1086: 최소 비용(DP)
메모리 제한: 32메가
특수 판제:아니오
제출: 3960
해결: 819
제목 설명:
어떤 노선에 N개의 기차역이 있는데 세 가지 거리의 노정이 있다. L1, L2, L3, 대응하는 가격은 C1, C2, C3.해당 관계식은 다음과 같습니다.
거리
0
승객이 이동하려는 두 역의 거리가 L3보다 클 때는 가운데 한 역에서 내린 뒤 표를 사서 타면 되므로 승객은 전체 과정에서 최소 두 장의 표를 살 수 있다.
지금 L1, L2, L3, C1, C2, C3 하나 드릴게요.그 다음은 승객 여정의 시작역과 종착역인 A B의 값이다.
그리고 N, N을 입력하여 이 노선의 전체 기차역 수를 입력한 다음에 N-1개의 정수를 입력하면 각각 이 노선의 첫 번째 역, 두 번째 역, 세 번째 역,......, N번째 역의 거리를 대표한다.
입력에 따라 승객이 A역에서 B역까지 출력하는 최소 비용.
입력:
데이터를 다음과 같은 형식으로 입력합니다.
L1 L2 L3 C1 C2 C3
A B
N
a[2]
a[3]
……
a[N]
출력:
여러 그룹의 테스트 데이터가 있을 수 있습니다. 한 그룹의 데이터에 대해
입력에 따라 승객이 A역에서 B역까지 출력하는 최소 비용.
샘플 입력:
1 2 3 1 2 3
1 2
2
2샘플 출력:
2출처:
2011년 청화대학 컴퓨터 연구 생기 시험 진제
아이디어:
동적 기획, 이 문제의 DP 과정은 01배낭과 약간 유사하다.
프로그램의 주체는 x에서 시작하여 매 점까지의 가장 짧은 시간을 순서대로 구하고 y가 끝날 때까지 한다.
욕심 알고리즘을 쓰면 안 된다. 한 걸음 한 걸음 가장 먼 길을 걷는 것이 반드시 가장 좋은 것은 아니기 때문이다.
코드:
#include <stdio.h>
#define N 1000
typedef long long LL;
int main(void)
{
int n, i, j, k, r;
LL a[N+1];
LL m[N+1];
int x, y;
LL L1, L2, L3, C1, C2, C3;
while (scanf("%lld%lld%lld%lld%lld%lld", &L1, &L2, &L3, &C1, &C2, &C3) != EOF)
{
scanf("%d%d", &x, &y);
scanf("%d", &n);
a[1] = 0;
for(i=2; i<=n; i++)
scanf("%lld", &a[i]);
if (x == y)
{
printf("0
");
continue;
}
if (x > y)
{
int tmp = x;
x = y;
y = tmp;
}
//for (i=1; i<=n; i++)
// printf("%lld ", a[i]);
//printf("
");
m[x] = 0;
for (i=x+1; i<=y; i++)
{
m[i] = 1;
m[i] <<= 62;
j = i-1;
while(j >= x && a[i]-a[j] <= L1)
j --;
j ++;
if (j != i && m[j]+C1 < m[i])
m[i] = m[j] + C1;
//printf("===1===i=%d, j=%d, m[i]=%lld
", i, j, m[i]);
k = j-1;
while(k >= x && a[i]-a[k] <= L2)
k --;
k ++;
if (k != j && m[k]+C2 < m[i])
m[i] = m[k] + C2;
//printf("===2===i=%d, k=%d, m[i]=%lld
", i, k, m[i]);
r = k-1;
while(r >= x && a[i]-a[r] <= L3)
r --;
r ++;
if (r != k && m[r]+C3 < m[i])
m[i] = m[r] + C3;
//printf("===3===i=%d, r=%d, m[i]=%lld
", i, r, m[i]);
}
printf("%lld
", m[y]);
}
return 0;
}
/**************************************************************
Problem: 1086
User: liangrx06
Language: C
Result: Accepted
Time:0 ms
Memory:912 kb
****************************************************************/이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 구현 천둥 제거 게임 상세 정보먼저 작은 메뉴를 표시하고 게임을 할지 여부를 선택하십시오.사용자가 종료를 선택하면 프로그램 실행이 끝나고, 사용자가 게임을 선택하면 지뢰 제거 위치 좌표를 입력하라는 메시지가 표시됩니다.사용자가 입력한 좌표가 바둑...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
