자갈 합병 문제 집계

13199 단어 ★ 알고리즘 입문동적 기획
1: 임의의 판 에는 N 개의 돌 이 쌓 여 있 습 니 다. 현 재 는 돌 을 질서 있 게 한 무더기 로 합 쳐 야 합 니 다. 규정 은 다음 과 같 습 니 다. 매번 에 임의의 2 개의 돌 만 이동 하여 합병 할 수 있 고 합병 비용 은 한 무더기 의 돌 수량 입 니 다.이 N 개의 돌 더 미 를 한 무더기 로 합 치 는 데 드 는 총 비용 이 가장 적 거나 가장 큰 알고리즘 을 설계 합 니 다.이런 문 제 는 비교적 간단 하 다. 바로 하 프 만 코딩 의 변형 이다. 욕심 산법 으로 가장 좋 은 해 를 구 할 수 있다.한 무더기 만 남 을 때 까지 가장 적은 두 무 더 기 를 골 라 새로운 더미 로 합 치 는 것 이다.증명 과정 은 하프 만 의 증명 과정 을 참고 할 수 있다.
2: 체인 합병 은 N 더미 의 모래 를 한 줄 로 배열 하고 그 번 호 는 1, 2, 3,..., N (N < = 100) 이다.모래 더미 마다 일정한 수량 이 있다.이제 N 더 미 를 모래 더미 로 만들어 야 합 니 다.병합 하 는 과정 은 매번 인접 한 모래 두 무 더 기 를 한 무더기 로 쌓 아 올 릴 수 밖 에 없 으 며, 이렇게 N - 1 회 병합 을 거 쳐 한 무더기 가 된다.합 리 적 인 병합 방법 을 찾 아 총 대 가 를 최소 화하 다.사고: 동적 계획 가설 dp [i] [j] 는 i 개 에서 j 개 합병 시의 최소 (최대) 대 가 를 나타 내 면 전달 공식 을 얻 을 수 있다.
dp[i][j]={0mini≤k마지막 결과 값 은 dp [0] [n - 1]
코드 는 다음 과 같 습 니 다:
#include
#include
#include
#include

using namespace std;

const int inf = 99999999;
const int N = 300;
int num[N], sum[N], n;
int dpmax[N][N], dpmin[N][N];

int main() {
    while(cin>>n) {
        int i,j,k,total;
        for(i = 0; i < n; i++) {
            cin>>num[i];
        }

        sum[0] = num[0];
        for(i = 1; i < n; i++) {
            sum[i] = sum[i-1] + num[i];
        }

        for(i = 0; i < n; i++) {
            for(j = i; j < n; j++) {
                dpmax[i][j]= -inf;
                dpmin[i][j] = inf;
            }
        }

        for(i = 0; i < n; i++) {
            dpmax[i][i] = 0;
            dpmin[i][i] = 0;
        }

        for(k = 1; k < n; k++) {//  
            for(i = 0; i + k < n; i++) {
                for(j = i; j < i + k; j++) {
                    if(i==0) total = sum[i+k];
                    else total = sum[i+k] - sum[i-1];
                    dpmax[i][i+k] = max(dpmax[i][i+k], dpmax[i][j] + dpmax[j+1][i+k] + total);
                    dpmin[i][i+k] = min(dpmin[i][i+k], dpmin[i][j] + dpmin[j+1][i+k] + total);
                }
            }
        }
        int resmax = dpmax[0][n-1];
        int resmin = dpmin[0][n-1];
        cout<"
"<return 0;
}

3: 환형 판이 돌 이 원형 으로 배열 되 어 있 고 나머지 조건 이 변 하지 않 는 다 면 가장 좋 은 값 은 무엇 일 까?
사고: 원형 이 서로 연결 되 어 있 기 때문에 모든 요 소 를 기점 으로 길이 가 n 인 n 개의 체인 문제 에 해당 합 니 다. 따라서 이 문 제 는 두 가지 해법 이 있 습 니 다. 1. 체인 을 뜯 어서 크기 가 2 * n 인 배열 을 설정 하고 값 은 1. n. 1. n 입 니 다. 그러면 하나의 체인 문 제 를 구성 할 수 있 습 니 다. 2. 동적 계획 중의 dp 의 의 미 를 바 꿀 수 있 습 니 다. 우 리 는 먼저 첫 번 째, dp 의 공식 과 체인 식 을 토론 합 니 다.같 지만 결 과 는 다 릅 니 다. 코드 는 다음 과 같 습 니 다.
#include
#include
#include
#include

using namespace std;

const int inf = 99999999;
const int N = 300;
int num[N], sum[N], n;
int dpmax[N][N], dpmin[N][N];

int main() {
    while(cin>>n) {
        int i,j,k,total;
        for(i = 0; i < n; i++) {
            cin>>num[i];
            num[i+n] = num[i]; //     
        }

        sum[0] = num[0];
        for(i = 1; i < 2*n; i++) {
            sum[i] = sum[i-1] + num[i];
        }

        for(i = 0; i < 2 * n; i++) {
            for(j = i; j < 2 * n; j++) {
                dpmax[i][j]= -inf;
                dpmin[i][j] = inf;
            }
        }

        for(i = 0; i < 2 * n; i++) {
            dpmax[i][i] = 0;
            dpmin[i][i] = 0;
        }

        for(k = 1; k < n; k++) {//  
            for(i = 0; i + k < 2 * n; i++) {
                for(j = i; j < i + k; j++) {
                    if(i==0) total = sum[i+k];
                    else total = sum[i+k] - sum[i-1];
                    dpmax[i][i+k] = max(dpmax[i][i+k], dpmax[i][j] + dpmax[j+1][i+k] + total);
                    dpmin[i][i+k] = min(dpmin[i][i+k], dpmin[i][j] + dpmin[j+1][i+k] + total);
                }
            }
        }
        int resmax = -inf;
        int resmin = inf;
        for(i = 0; i + n - 1 < 2 * n; i++) {//        
            resmax = max(resmax,dpmax[i][i+n-1]);//   n
            resmin = min(resmin,dpmin[i][i+n-1]);//   n
        }
        cout<"
"<return 0;
}

주의: 순환 할 때 길 이 는 1 에서 n 까지 이 고 마지막 결 과 는 모든 요소 가 기점 길이 가 n 의 가장 작은 값 중 가장 작은 것 입 니 다.
사고 2: dp [i] [j] 를 설정 하면 i 부터 길이 가 j 의 한 단락 이 합 쳐 진 후의 최소 (최대) 값 을 나타 낸다. 그러면 j 의 최대 n 은 다음 과 같다.
dp[i][j]={0min{dp[i][k]+dp[(i+k+1)%n][j−k−1]+sum(i,j)}j=00≤k그 중:
sum[i][j]=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪∑k=ijstone[k]∑k=in−1stone[k]+∑k=0(i+j)%nstone[k]i+j마지막 결 과 는 모든 요소 가 출발점 길이 n 의 최소 값 중 가장 작은 것 입 니 다.
코드 는 다음 과 같 습 니 다:
#include
#include
#include

using namespace std;

const int inf = 99999999;
const int N = 300;

int dpmin[N][N];
int dpmax[N][N];
int sum[N], a[N];
int resmin, resmax;
int n;

int getsum(int i, int len) // i   len 
{
    if(i + len >= n) return getsum(i,n-i-1) + getsum(0,(i+len) % n);
    else return sum[i+len] - (i > 0 ? sum[i-1] : 0);
}

void func(int a[], int n)
{
    for(int i = 0; i < n; i++)
        dpmin[i][0] = dpmax[i][0] = 0;

    for(int j = 1; j < n; j++)
    {
        for(int i = 0; i < n; i++)
        {
            dpmin[i][j] = inf;
            dpmax[i][j] = -inf;
            for(int k = 0; k < j; k++)
            {
                dpmin[i][j] = min(dpmin[i][j], dpmin[i][k] + dpmin[(i+k+1) % n][j - k - 1] + getsum(i,j));
                dpmax[i][j] = max(dpmax[i][j], dpmax[i][k] + dpmax[(i + k + 1) % n][j - k - 1] + getsum(i,j));
            }
        }
    }
    resmin = dpmin[0][n-1];
    resmax = dpmax[0][n-1];

    for(int i = 0; i < n; i++)
    {
        resmin = min(resmin, dpmin[i][n-1]);
        resmax = max(resmax, dpmax[i][n-1]);
    }
}

int main()
{
    freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);
    }
    sum[0] = a[0];
    for(int i = 1; i < n; i++)
    {
        sum[i] = sum[i-1] + a[i];
    }
    func(a,n);
    printf("%d %d
", resmin,resmax);

    return 0;
}
[Behavioral Patterns] - Memento
PL/SQL Blocks

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage