글 읽기 - 어떤게 틀렸는지 모르겠습니다...

crasy111 7년 전 0

D[i][j]를 1~j까지의 원소중,k~j까지의 원소를 i번째 그룹에, 그리고 k-2까지를 i-1개의 그룹으로 나눴을때의 최대값

으로 점화식을 세우고 dp를 돌렸는데 틀렸습니다...

점화식이 틀린건가요...?

아래는 제 소스코드입니다.

#include<bits/stdc++.h>

using namespace std;

int n,m,dy[55][105],arr[105],sum[105];

int main()
{
    scanf("%d%d",&n,&m);
    int i,j,k,ans=-999999999;
    for(i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        sum[i]=sum[i-1]+arr[i];
    }
    for(i=1;i<=m;i++) for(j=0;j<=n;j++) dy[i][j]=-999999999;
    for(i=1;i<=n;i++){
        dy[1][i]=arr[i];
        for(j=1;j<i;j++){
            if(sum[i]-sum[j-1]>dy[1][i]) dy[1][i]=sum[i]-sum[j-1];
        }
    }
    for(i=2;i<=m;i++){
        for(j=2;j<=n;j++){
            dy[i][j]=dy[i-1][j-2]+arr[j];
            for(k=j-2;k>=1;k--) dy[i][j]=max(dy[i][j],dy[i-1][k]+(sum[j]-sum[k+1]));
        }
    }
    for(i=1;i<=n;i++){
        if(dy[m][i]>ans) ans=dy[m][i];
    }
    printf("%d",ans);
    return 0;
}

yukariko 7년 전 2

위 코드에서는 정확하게 한칸만을 건너뛰지만

여러 칸을 건너뛰는것도 답이 될 수 있습니다.

3 2 -1 -2 -3 3

같은 입력에서는 -1 -2 -3을 한번에 건너뛰는것이 이득입니다.

물론 M을 만족하는 경우에서요.

crasy111 7년 전 0

아...

k를 이용해서 여러칸 건너뛰는거 처리했다고 생각해버렸네요...ㅠ

갓카리코님 감사합니다

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

문제

문제

출처

ICPC

어떤게 틀렸는지 모르겠습니다...

crasy111 7년 전 0

yukariko 7년 전 2

crasy111 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말