글 읽기 - 질문합니다.

sgc109 8년 전 0

D(i) = i일째까지 모두 탔을때 최소비용(i>=1)

D(i) = min(

D(i-1)+bus[i]*1+train[i]*2,

D(i-1)+3+train[i]*2,

D(i-1)+6,

D(i-7)+18+sum(train[i-6]~train[i])*2,

D(i-7)+36,

D(i-30)+45+sum(train[i-29]~train[i])*2,

D(i-30)+90

)

이렇게 짜봤는데 틀렸다고나오는데 틀린이유를 잘 모르겠습니다.

(위에서 만약 D(i-x) 나 train[i-x] 같은데서 인덱스가 음수면 0 또는 0부터더하는걸로 바꿉니다.)

#define REP(i,a,b) for(int i = a;i < b; ++i)
#define FOR(i,n) REP(i,0,n)
#define LONG long long
#define INFL 0x7fffffffffffffff
 
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
 
using namespace std;

int inRange(int x) {
    if(x < 0) return 0;
    return x;
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n;
        scanf("%d",&n);
        int train[10000];
        int bus[10000];
        int trainAcc[10001];
        int dp[10001];
        trainAcc[0] = 0;
        FOR(i,n) {
            scanf("%d%d",bus+i,train+i);
            trainAcc[i+1] = trainAcc[i]+train[i];
        }
        dp[0] = 0;
        REP(i,1,n+1) {
            dp[i] = min(dp[i-1]+bus[i-1]+train[i-1]*2,dp[i-1]+3+train[i-1]*2);
            dp[i] = min(dp[i],dp[i-1]+6);
            dp[i] = min(dp[i],dp[inRange(i-7)]+18+2*(trainAcc[i]-trainAcc[inRange(i-7)]));
            dp[i] = min(dp[i],dp[inRange(i-7)]+36);
            dp[i] = min(dp[i],dp[inRange(i-30)]+45+2*(trainAcc[i]-trainAcc[inRange(i-30)]));
            dp[i] = min(dp[i],dp[inRange(i-30)]+90);
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

nuclear852 8년 전 1

sum (train [k] - train [j]) * 2 부분을 더하는 것이 잘못 된 것 같은데..

30일 버스 이용권을 샀을 때,

굳이 남은 30일 동안 train을 1회이용권만 사라는 법은 없잖아요??

예를 들어서

Day 1 2 3 4 5 6 7 8 9 .... 30

bus max회 max회 .... max회

train 4회 4회 4회 4회 4회 4회 4회 0회 0회 ... 0회

이럴경우는 30일 버스 이용권 + 7일 freepass 81달러로 사는게 제일 이득인데

train을 1회 이용권 사는 것 말고도 free pass를 구매하여 이득을 보는 경우를 고려해야 할 것 같아용...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문합니다.

sgc109 8년 전 0

nuclear852 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말