dp훈련 제12문제vijos1037 쌍탑 구축 dp

n(100)과 n개수(2000을 넘지 않음)를 주고 이 수의 일부분 또는 전부를 두 개의 상등수로 조합할 수 있는지 물어보세요. 최대는 얼마입니까?
먼저 떠오르는 것은 표시할 수 있는 모든 수를 매거하는 것이다. 즉, 2차원 상태 표시: dp[i][j]는 i와 j를 구성할 수 있는지를 나타낸다. 결과는 0<=i<=1000에 대해 가장 큰 i를 취하면 dp[i][i]=1 경계 조건: dp[0][0]=1 상태 이동: 이전 이전, dp[i][j]=dp[i-save[k]]][j]|dp[i][j-save[k]]]]][j]]]]를 나타낸다.save[k]는 k번째 숫자를 나타냅니다.
1000*1000*100 때문에 시간을 초과하는 느낌도 있어요.하지만 겨우 지나쳤으니 최적화가 잘 된 것 같다

    int n=read();
    for(int i=1;i<=n;i++)
        save[i]=read();
    dp[0][0]=1;
    for(int k=1;k<=n;k++)
        for(int i=1000;i>=0;i--)
            for(int j=1000;j>=0;j--)
                dp[i+save[k]][j]|=dp[i][j],dp[i][j+save[k]]|=dp[i][j];
    int ans=0;
    for(int i=1000;i>=0;i--)
        if(dp[i][i])
            ans=i,i=-1;
    if(ans)
        printf("%d
",ans );
    else
        printf("Impossible
");

두 번째 방법은 문제풀이에서 나온 것으로 교묘한 방법으로 조금 쓰기 어렵다.상태 표시: dp[i][j]: i번째 숫자를 뽑은 후 대수와 소수의 차이가 j일 때 가장 큰 대수를 나타낸다. 결과: dp[n][0]상태 이동: 뒤로 이동, dp[i][j]는 네 가지 상태로 이동할 수 있고 i번째 수에 대응하는 네 가지 처리 방식 1.이 수를 넣지 않습니다 dp[i+1] [j]=dp[i][j]2.비교적 큰 수에 dp[i+1][j+save[i+1]=dp[i][j]+save[i+1]3.비교적 소수에 놓고 대수(j>=save[i+1]) dp[i+1] [j-save[i+1]=dp[i][j]4.비교적 소수에 놓고 큰 수를 초과한다(j경계 상황: dp[i][j]=-1, dp[0][0]=0
WA점1: 처음에 이전이전으로 썼는데 i와 j가 너무 복잡해서 나를 어지럽게 했다. WA점2: 결과가 0인 경우impossible를 출력해야 한다.

    int n=read();
    for(int i=1;i<=n;i++)
        save[i]=read();
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=2000;j++)
    {
        if(dp[i][j]==-1) continue;
        dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
        dp[i+1][j+save[i+1]]=max(dp[i+1][j+save[i+1]],dp[i][j]+save[i+1]);
        if(j>=save[i+1])
            dp[i+1][j-save[i+1]]=max(dp[i+1][j-save[i+1]],dp[i][j]);
        else
            dp[i+1][save[i+1]-j]=max(dp[i+1][save[i+1]-j],dp[i][j]+save[i+1]-j);
    }
    if(dp[n][0])
        printf("%d
",dp[n][0] );
    else
        printf("Impossible
");

이 문제는 적어도 세 가지를 배울 수 있다. 하나는 매거 상태이고 동시에 두 가지를 매거할 수 있으며 어떤 상황에서도 가능하다.하나는 간소화 상태이다. 예를 들어 이 문제에서 두 수의 차이만 기록하면 된다.하나는'이전이전이전이전'과'후이전'의 생각과 쓰기 방법이다. 일반적으로 이전이전이전이전이전은 생각하기 어렵지만 편리하다. 뒤로 잘 옮기면 표시하지만 -1을 두어야 한다. 이 점에 대해 나는 아직도 의문이 있다. 앞으로 계속 정리할 것이다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

49일차 - 2022.04.20

Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

dp훈련 제12문제vijos1037 쌍탑 구축 dp

좋은 웹페이지 즐겨찾기