글 읽기 - 여기있는 반례 다해봤는데 왜 틀렸는지 모르겠습니다...

peterjdw 2년 전 0

테스트케이스랑 질문글 반례들 다넣어봐도 제대로 값이 나오는데
25퍼에서 계속 틀립니다..이유가 뭘까요?
도와주십시오..
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <vector>
#include <limits.h>

using namespace std;
#define INF (INT_MAX-100)

//DP1: 1번과 마지막칸 위아래 다연결
//DP2: 1번과 마지막칸 위가 연결
//DP3: 1번과 마지막칸 아래가 연결
//DP4: 1번과 마지막칸 안연결

int UP[10005];
int DOWN[10005];

int DP1[5][10005];
int DP2[5][10005];
int DP3[5][10005];
int DP4[5][10005];


int min(int a, int b, int c, int d){
    return min(min(a,b),min(c,d));
}

int min(int a, int b, int c, int d,int e){
    return min(min(min(a,b),min(c,d)),e);
}



int main(void){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int T, N, W;
    cin>>T;
    for(int a=0;a<T;a++){
        cin>>N>>W;
        int d1=INF, d2=INF, d3=INF, d4=INF;
        for(int i=1;i<=N;i++){
            cin>>UP[i];
        }
        for(int i=1;i<=N;i++){
            cin>>DOWN[i];
        }
        if(N==1){
            if(UP[1]+DOWN[1]<=W) cout<<1<<"\n";
            else cout<<2<<"\n";
        }else{
            int upC=0, doC=0, colC=0;
            
            //DP1이 가능한가?
            if(W>=UP[1]+UP[N] && W>=DOWN[1]+DOWN[N]){
                DP1[0][1]=2;
                DP1[1][1]=INF;
                DP1[2][1]=INF;
                DP1[3][1]=INF;
                DP1[4][1]=INF;
                for(int i=2;i<=N-1;i++){
                    if((UP[i]+UP[i-1])<=W) upC=1;
                    if((DOWN[i]+DOWN[i-1])<=W) doC=1;
                    if((UP[i]+DOWN[i])<=W) colC=1;

                    //0row는 앞거랑 위아래가 다 이어질때
                    if(upC&&doC&&DP1[4][i-1]!=INF) DP1[0][i]=DP1[4][i-1];
                    else DP1[0][i] = INF;
                    //1row는 앞거랑 아래가 이어질때
                    if(doC && (DP1[2][i-1] != INF || DP1[4][i-1] != INF)) DP1[1][i] = min(DP1[2][i-1],DP1[4][i-1])+1;
                    else DP1[1][i] = INF;
                    //2row는 앞거랑 위가 이어질때
                    if(upC && (DP1[1][i-1] != INF || DP1[4][i-1] != INF)) DP1[2][i] = min(DP1[1][i-1],DP1[4][i-1])+1;
                    else DP1[2][i] = INF;
                    //3row는 앞거랑 안이어지고 i의 위아래가 연결될때
                    if(colC) DP1[3][i] = min(DP1[0][i-1],DP1[1][i-1],DP1[2][i-1],DP1[3][i-1],DP1[4][i-1])+1;
                    else DP1[3][i] = INF;
                    //4row는 그냥 따로따로 한분대씩 집어넣기
                    DP1[4][i] = min(DP1[0][i-1],DP1[1][i-1],DP1[2][i-1],DP1[3][i-1],DP1[4][i-1])+2;

                    upC=0;
                    doC=0;
                    colC=0;
                }
                d1=min(DP1[0][N-1],DP1[1][N-1],DP1[2][N-1],DP1[3][N-1],DP1[4][N-1]);
            }

            //DP2가 가능한가?
            if (W>=UP[1]+UP[N]){
                DP2[0][1]=INF;
                DP2[1][1]=INF;
                DP2[2][1]=2;
                DP2[3][1]=INF;
                DP2[4][1]=INF;
                for(int i=2;i<=N-1;i++){
                    if((UP[i]+UP[i-1])<=W) upC=1;
                    if((DOWN[i]+DOWN[i-1])<=W) doC=1;
                    if((UP[i]+DOWN[i])<=W) colC=1;

                    //0row는 앞거랑 위아래가 다 이어질때
                    if(upC&&doC&&DP2[4][i-1]!=INF) DP2[0][i]=DP2[4][i-1];
                    else DP2[0][i] = INF;
                    //1row는 앞거랑 아래가 이어질때
                    if(doC && (DP2[2][i-1] != INF || DP2[4][i-1] != INF)) DP2[1][i] = min(DP2[2][i-1],DP2[4][i-1])+1;
                    else DP2[1][i] = INF;
                    //2row는 앞거랑 위가 이어질때
                    if(upC && (DP2[1][i-1] != INF || DP2[4][i-1] != INF)) DP2[2][i] = min(DP2[1][i-1],DP2[4][i-1])+1;
                    else DP2[2][i] = INF;
                    //3row는 앞거랑 안이어지고 i의 위아래가 연결될때
                    if(colC) DP2[3][i] = min(DP2[0][i-1],DP2[1][i-1],DP2[2][i-1],DP2[3][i-1],DP2[4][i-1])+1;
                    else DP2[3][i] = INF;
                    //4row는 그냥 따로따로 한분대씩 집어넣기
                    DP2[4][i] = min(DP2[0][i-1],DP2[1][i-1],DP2[2][i-1],DP2[3][i-1],DP2[4][i-1])+2;

                    upC=0;
                    doC=0;
                    colC=0;
                }
                //만약 n과 n-1 down이 된다면 n-1의 row2나 row4 그대로쓰고 아니면 모든row에 +1해주면된다.
                if((DOWN[N]+DOWN[N-1])<=W){
                    d2 = min(DP2[0][N-1]+1,DP2[1][N-1]+1,DP2[2][N-1],DP2[3][N-1]+1,DP2[4][N-1]);
                }
                else{
                    d2 = min(DP2[0][N-1],DP2[1][N-1],DP2[2][N-1],DP2[3][N-1],DP2[4][N-1])+1;
                }

            }


            //DP3이 가능한가?
            if(W>=DOWN[1]+DOWN[N]){
                DP3[0][1]=INF;
                DP3[1][1]=2;
                DP3[2][1]=INF;
                DP3[3][1]=INF;
                DP3[4][1]=INF;
                for(int i=2;i<=N-1;i++){
                    if((UP[i]+UP[i-1])<=W) upC=1;
                    if((DOWN[i]+DOWN[i-1])<=W) doC=1;
                    if((UP[i]+DOWN[i])<=W) colC=1;

                    //0row는 앞거랑 위아래가 다 이어질때
                    if(upC&&doC&&DP3[4][i-1]!=INF) DP3[0][i]=DP3[4][i-1];
                    else DP3[0][i] = INF;
                    //1row는 앞거랑 아래가 이어질때
                    if(doC && (DP3[2][i-1] != INF || DP3[4][i-1] != INF)) DP3[1][i] = min(DP3[2][i-1],DP3[4][i-1])+1;
                    else DP3[1][i] = INF;
                    //2row는 앞거랑 위가 이어질때
                    if(upC && (DP3[1][i-1] != INF || DP3[4][i-1] != INF)) DP3[2][i] = min(DP3[1][i-1],DP3[4][i-1])+1;
                    else DP3[2][i] = INF;
                    //3row는 앞거랑 안이어지고 i의 위아래가 연결될때
                    if(colC) DP3[3][i] = min(DP3[0][i-1],DP3[1][i-1],DP3[2][i-1],DP3[3][i-1],DP3[4][i-1])+1;
                    else DP3[3][i] = INF;
                    //4row는 그냥 따로따로 한분대씩 집어넣기
                    DP3[4][i] = min(DP3[0][i-1],DP3[1][i-1],DP3[2][i-1],DP3[3][i-1],DP3[4][i-1])+2;

                    upC=0;
                    doC=0;
                    colC=0;
                }
                //만약 n과 n-1 down이 된다면 n-1의 row1이나 row4 그대로쓰고 아니면 모든row에 +1해주면된다.
                if((UP[N]+UP[N-1])<=W){
                    d2 = min(DP3[0][N-1]+1,DP3[1][N-1],DP3[2][N-1]+1,DP3[3][N-1]+1,DP3[4][N-1]);
                }
                else{
                    d2 = min(DP3[0][N-1],DP3[1][N-1],DP3[2][N-1],DP3[3][N-1],DP3[4][N-1])+1;
                }

            }


            //DP4 이친구는 처음과 끝이 관련이 없다. 선형으로 생각하면 편하다.
            if(true){
                if((UP[1]+DOWN[1])<=W) DP4[3][1]=1;
                else DP4[3][1]=INF;
                DP4[0][1]=INF;
                DP4[1][1]=INF;
                DP4[2][1]=INF;
                DP4[4][1]=2;
                for(int i=2;i<=N;i++){
                    if((UP[i]+UP[i-1])<=W) upC=1;
                    if((DOWN[i]+DOWN[i-1])<=W) doC=1;
                    if((UP[i]+DOWN[i])<=W) colC=1;

                    //0row는 앞거랑 위아래가 다 이어질때
                    if(upC&&doC&&DP4[4][i-1]!=INF) DP4[0][i]=DP4[4][i-1];
                    else DP4[0][i] = INF;
                    //1row는 앞거랑 아래가 이어질때
                    if(doC && (DP4[2][i-1] != INF || DP4[4][i-1] != INF)) DP4[1][i] = min(DP4[2][i-1],DP4[4][i-1])+1;
                    else DP4[1][i] = INF;
                    //2row는 앞거랑 위가 이어질때
                    if(upC && (DP4[1][i-1] != INF || DP4[4][i-1] != INF)) DP4[2][i] = min(DP4[1][i-1],DP4[4][i-1])+1;
                    else DP4[2][i] = INF;
                    //3row는 앞거랑 안이어지고 i의 위아래가 연결될때
                    if(colC) DP4[3][i] = min(DP4[0][i-1],DP4[1][i-1],DP4[2][i-1],DP4[3][i-1],DP4[4][i-1])+1;
                    else DP4[3][i] = INF;
                    //4row는 그냥 따로따로 한분대씩 집어넣기
                    DP4[4][i] = min(DP4[0][i-1],DP4[1][i-1],DP4[2][i-1],DP4[3][i-1],DP4[4][i-1])+2;

                    upC=0;
                    doC=0;
                    colC=0;
                }
                d4 = min(DP4[0][N],DP4[1][N],DP4[2][N],DP4[3][N],DP4[4][N]);
            }
            cout<<min(d1,d2,d3,d4)<<"\n";
        
        }
    }

    
}
bamgoesn 2년 전 1

https://www.acmicpc.net/board/...
첨부한 반례를 참고해주세요
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

여기있는 반례 다해봤는데 왜 틀렸는지 모르겠습니다...

peterjdw 2년 전 0

bamgoesn 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
