[낙곡P1880] [NOI1995] 돌멩이 합병

구간 DP 템플릿 문제
구간 DP 템플릿 코드:

for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=2*n-1;i++)  //      
        {
            int j = i + len - 1;  //      
            for(int k=i;k//     
            {
                f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }

 
제목 설명
한 원형 운동장의 주위에 N더미의 돌을 놓았는데, 지금은 돌을 순서대로 한 무더기로 합쳐야 한다.매번 인접한 2더미만 골라 새 더미로 합쳐 새 돌무더기의 수를 이번 합병의 득점으로 기록하도록 했다.
하나의 알고리즘을 시험적으로 설계하여 N더미의 돌을 1더미로 합친 최소 득점과 최대 득점을 계산해 냈다.
입력 출력 형식
입력 형식:
데이터의 제1행은 정수 N, 1≤N≤100을 시험하여 N더미의 돌을 나타낸다.두 번째 줄에는 N개의 수가 있는데, 각각 돌무더기의 개수를 나타낸다.
출력 형식:
출력 총 2행, 제1행위 최소 득점, 제2행위 최대 득점.
출력 샘플 가져오기
샘플 입력 #1:4 4 5 9 4
샘플 내보내기 #1:43 54
이 문제의 데이터 저장 특징은 대표적이다. 파환이 열을 이루고 길이가 n인 고리를 길이가 2n-1인 열로 바꾸어 다시 한 번 동귀한다.
이 문제에 대한 n은 매우 작기 때문에 우리는 그것으로 구간의 길이를 대표할 수 있다. 이렇게 하면 O(n^3)도 달릴 수 있다
구간DP의 개념은 한 구간의 상태를 그 하위 구간의 상태로 계속 분할하는 것이다. 이 하위 구간의 상태까지는 분명히 구할 수 있는 것이고 마지막에 그것들을 종합하는 것이다.
밤을 들다.
f[i][j]에서 우리는 [i, j]라는 구간을 [i, k]와 [k+1, j] 두 구간의 전체 상태로 나누어 다시 한 번 조작할 수 있다.
이 경계는 바로 [i,k]와 [k+1,j]가 분명히 구할 수 있는 상태이다
이 문제는 최대치와 최소치를 요구하는 문제입니다.
우리는 최소치가 반드시 최대치보다 작다는 것을 명백히 발견할 수 있다
이렇게 하면 우리는 하나의 수조만 세울 수 있다. 먼저 가장 작은 것을 구하고 최대를 구하며 두 개의 수조의 공간을 절약할 수 있다. (이것은 중점 qwq가 아니지만)
Code:
 

#include
#include
#include
#include 
using namespace std;
int f[300][300];  //     
int s[300];
int n,x,ans = 55312725;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        s[i] = s[i - 1] + x;
        s[i + n] = s[i];  //      2n - 1 
    }
    for(int i=1;i)
    s[i + n] += s[n];
    memset(f,10,sizeof(f));  //    
    for(int i=1;i<=2*n-1;i++)
    f[i][i] = 0;
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=2*n-1;i++)  //      
        {
            int j = i + len - 1;  //      
            for(int k=i;k//     
            {
                f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    ans = min(ans,f[i][i + n - 1]);
    printf("%d
",ans);  //           ，       
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=2*n-1;i++)  //      
        {
            int j = i + len - 1;  //      
            for(int k=i;k//     
            {
                f[i][j] = max(f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    ans = max(ans,f[i][i + n - 1]);
    printf("%d
",ans);
    return 0; 
}

 
전재 대상:https://www.cnblogs.com/lyp-Bird/p/10731672.html