Poj 1050 동적 계획

제목 대의: 사각형 행렬 에 요소 와 최대 의 서브 행렬 을 구 해 줍 니 다.최종 출력 최대 와 결 과 를 요구 합 니 다.
제목 분석: 한 배열 의 최대 와 동적 계획 을 통 해 잘 해결 되 고 다음 과 같은 전달 공식 을 이용 하면 된다.
dp[i]=max{dp[i−1]+A[i],A[i]}
그러나 이것 은 2 차원 의 문제 다.
처음에 동태 계획 의 사상 에 따라 나 는 문 제 를 가장 좋 은 문제 로 귀결 시 키 기 를 기 대 했 지만 실패했다.나중에 문 제 를 1 차원 배열 로 계획 하여 해결 하 는 것 이 좋 았 다.구체 적 인 방법 은 행렬 의 연속 행 을 합 쳐 1 차원 배열 로 바 꾸 어 최대 하위 문자열 과 합 을 구 하 는 것 이다.4 * 4 의 행렬 을 예 로 들 면 연속 줄 을 더 한 것 은 4 + 3 + 2 + 1 가지 가 있 는데 각각 한 줄, 두 줄, 세 줄, 네 줄 의 상황 이다.우 리 는 10 개의 1 차원 배열 을 얻어 최대 하위 문자열 과 구 할 수 있 고 최종 적 으로 가장 큰 결 과 를 선택 하면 된다.
생각 이 뚜렷 해 졌 지만 코드 가 여러 번 없어 진 이 유 는 시간 을 초과 한 것 이다.이전의 사고방식 은 이렇다. i 를 한 줄, 두 줄, 세 줄, 네 줄 로 순환 하 는 상황 이다.내부 순환 j 는 끝 줄 입 니 다.하나의 배열 B 저장 결 과 를 정의 하고 각 줄 의 k 열 에 대해 k 는 다시 순환 합 니 다.그리고 k 번 째 요 소 는 j - i 줄 에서 j 줄 로 추가 해 야 합 니 다. 이것 은 또 하나의 순환 이 필요 합 니 다.모두 4 층 순환 인 데, 이것 은 틀림없이 시간 을 초과 한 것 이다.
나중에 개선 되 어 3 층 순환 이 되 었 다.i 와 j 를 다시 정의 하고 i 를 시작 줄, j 를 끝 줄 로 정의 합 니 다.이렇게 하면 i 는 1 에서 N, j 는 i 에서 N 까지 모든 상황 을 옮 겨 다 닐 수 있다.ij 내부 에서 k 순환 을 정의 하고 B [k] + = A [j] [k] 를 계산 합 니 다.이렇게 j 가 증가 함 에 따라 B [k] 는 여러 줄 의 합 이 되 고 i 를 바 꿀 때 B 를 초기 화하 면 됩 니 다.이렇게 해서 3 층 순환 이 되 어 순조롭게 통과 되 었 다.이 프로그램의 설 계 는 좀 더 고려 해 야 한 다 는 것 을 알 수 있다.

#include 
#include 

using namespace std;

int N;
int A[510][510];
int B[510];
int dp[510];
int ans = -9999;
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < N; i++)
    {
        memset(B,0, sizeof(B));
        for (int j = i; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                B[k] += A[j][k];
                if (!k)
                    dp[0] = B[0];
                else
                    dp[k] = dp[k - 1]>0 ? dp[k - 1] + B[k] : B[k];
                ans = dp[k] > ans ? dp[k] : ans;
            }
        }
    }
    cout << ans << endl;
    //system("pause");
    return 0;
}