글 읽기 - 시간초과....

wjd86347 3년 전 0

점화식은 잘 구현한 것 같은데, 중간정도에서 시간초과가 발생합니다. 무엇이 문제일까요?

#include <cstdio>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef long long int ll;
int n,m;
int cost[1002][1002];
ll dp_int[1002][1002];
ll dp_float[1002][1002][2];
ll ans = 0;
ll ans2 = 0;

ll dfs_dp_float_up(int x,int y);
ll dfs_dp_float_down(int x,int y);


bool is_in(int x,int y){
    return 0<=x && x<= n+1 && 0<=y && y<=m+1;
}

ll dfs_dp_int (int x, int y){
    //나가는경우
    if(!is_in(x,y)) return 0;

    //dp
    if(dp_int[x][y]) return dp_int[x][y];

    //상하
    ll tmp = max(dfs_dp_int(x-1,y-1),dfs_dp_int(x+1,y-1));

    //dp값 저장 및 return
    return  dp_int[x][y] = max(tmp,dfs_dp_int(x,y-2)+cost[x][y-1])+cost[x][y];
}


ll dfs_dp_float_up(int x,int y){
    if(!is_in(x,y)) return 0;
    if(dp_float[x][y][0]) return dp_float[x][y][0];
    return dp_float[x][y][0] = max(dfs_dp_float_up(x+1,y-1),dfs_dp_float_down(x,y-1))+cost[x][y];
}


ll dfs_dp_float_down(int x,int y){
    if(!is_in(x,y)) return 0;
    if(dp_float[x][y][1]) return dp_float[x][y][1];
    return dp_float[x][y][1] =  max(dfs_dp_float_down(x-1,y-1),dfs_dp_float_up(x,y-1))+cost[x][y];
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) {
            scanf("%d",&cost[i][j]);
        }
    }
    
    for(int i=1;i<=n;i++) ans = max(ans,dfs_dp_int(i,m+1));
   


    for(int i=1;i<=n;i++){
        ans2 = max(ans2,dfs_dp_float_up(i,m+1));
        ans2 = max(ans2,dfs_dp_float_down(i,m+1));
    }

    printf("%lld\n",max(ans,ans2));
    return 0;
}

djm03178 3년 전 1

dp 값이 0인 경우 계산되지 않은 경우와 0으로 계산이 된 경우를 구분할 수 없습니다. 이미 전에 계산해놓고도 dp값이 계속 0이기 때문에 재귀호출 될 때마다 또다시 재계산을 하게 됩니다.

wjd86347 3년 전 0

-1로 처리하니깐 통과하였습니다 감가합니다!!

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

문제

문제

출처

ICPC

시간초과....

wjd86347 3년 전 0

djm03178 3년 전 1

wjd86347 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말