SDNUOJ 1048 石子合并2（區間動态規劃）

題目描述

有n堆石子排成一圈，每次選擇相鄰的兩堆石子，将其合并為一堆，記錄該次合并的得分為兩堆石子個數之和。已知每堆石子的石子個數，求當所有石子合并為一堆時，最小的總得分。

Input

第一行一個整數n(1 <= n <= 200)，表示石子堆數； 第二行n個整數a(1 <= a <= 100)，表示每堆石子的個數，這些石子首尾相接排成一圈。

Output

一個整數，表示最小總得分。

Sample Input

5

7 6 5 7 100

Sample Output

175

解析

它其實是這道題（石子合并1）的變形。

我們隻要改變石子合并1的狀态轉移方程即可。

機率環形問題的區間問題，存在這樣的情況，假設石子堆為4個，即我們的最優區間可能是3,4,1,2。

方法一

這樣的情況是線性石子堆無法解決的，因為線性石子堆我們隻需考慮1,2,3,4的區間最優即可。是以我們的外循環就不是長度了，而變為開始區間的索引，内循環則為從這個區間開始往後數幾個，然後k則為劃分這個區間。是以狀态轉移方程為：

dp[i][j]=0,j=1 d p [ i ] [ j ] = 0 , j = 1

dp[i][j]=min{dp[i][j],dp[i][k]+dp[(i+k−1)%n][j−k]+sum[i,j]} d p [ i ] [ j ] = m i n { d p [ i ] [ j ] , d p [ i ] [ k ] + d p [ ( i + k − 1 ) % n ] [ j − k ] + s u m [ i , j ] }

以上方程，隻需注意兩點：

1. (i + k - 1) \% n 表示的是k劃分後，我們的另一個區間的開始的位置，這裡我們先要求出第一個區間的末尾位置，取餘後再加1，是為了應付這種情況，即假設n = 5, i= 2，k = 3, 如果直接（i+k) % 5 = 0, 顯示不對的，第二個區間位置應該是5，是以先減一，再加1

2. sum(i,j)， 根據因為此處j指的是區間元素個數， 然後計算區間和。

static int getSum(int index, int length){
        int sum = ;
        for(int i = ; i <= length; i++){
            sum += nums[index];
            index++;
            if(index > n){
                index = ;
            }
        }
        return sum;
    }
           

方法一代碼

package com.special.SDNUOJ;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by Special on 2018/6/4 11:30
 */
public class SDNUOJ1048 {

    static int[] nums;
    static int n;
    static int[][] dp;

    static int getSum(int index, int length){
        int sum = ;
        for(int i = ; i <= length; i++){
            sum += nums[index];
            index++;
            if(index > n){
                index = ;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            n = input.nextInt();
            nums = new int[n + ];
            dp = new int[n + ][n + ];
            for(int i = ; i <= n; i++) {
                nums[i] = input.nextInt();
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }
            for(int j = ; j <= n; j++){
                for(int i = ; i <= n; i++){
                    int sum = getSum(i, j);
                    dp[i][] = ;
                    for(int k = ; k < j; k++){
                        dp[i][j] = Math.min(dp[i][j],
                                dp[i][k] + dp[(i + k - ) % n + ][j - k] + sum);
                    }
                }
            }
            int ans = Integer.MAX_VALUE;
            for(int i = ; i <= n; i++){
                ans = Math.min(ans, dp[i][n]);
            }
            System.out.println(ans);
        }
    }
}
           

方法二

既然環形的區間可能從任意位置開始，是以我們可以化環形為直線型問題，問題轉為石子合并1問題，轉換方法為把目前的石子堆複制一份放到後面，這樣就可以了。

為了減少不必要的計算問題，比如n = 4. 我們再求dp[5][6]的最優值，其實它與dp[1][2]是等價，故而我們隻需求dp[4][…]的最優區間即可，dp[5+]之後就不用考慮，但是這樣在求dp[3][6]最優區間的值時，遇到劃分dp[3][4] 和dp[5][6]，這時我們就要把dp[5][6]轉化為dp[1][2]。因為上面我們隻算到打破dp[4]開頭的最優區間，後面的就沒算。

方法二代碼

package com.special.SDNUOJ;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by Special on 2018/6/4 11:51
 */
public class SDNUOJ1048_02 {

    static int[] nums, sum;
    static int n;
    static int[][] dp;

    static int getSum(int i, int j){
        int result = ;
        if(j > n){
            result = sum[j % n] + sum[n] - sum[i - ];
        }else {
            result = sum[j] - sum[i - ];
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            n = input.nextInt();
            dp = new int[ * n + ][ * n + ];
            nums = new int[ * n + ];
            sum = new int[n + ];
            for(int i = ; i <= n; i++){
                nums[i] = input.nextInt();
                nums[n + i] = nums[i];
                sum[i] = sum[i - ] + nums[i];
            }
            for(int i = ; i <=  * n; i++){
                Arrays.fill(dp[i], Integer.MAX_VALUE);
                dp[i][i] = ;
            }
            for(int len = ; len < n; len++){
                for(int i = ; i <= n; i++){
                    int j = i + len;
                    int sum = getSum(i, j);
                    for(int k = i; k < j; k++){
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] +
                                (k >= n ? dp[(k + ) % n][j % n] : dp[k + ][j]) + sum);
                    }
                }
            }
            int result = Integer.MAX_VALUE;
            for(int i = ; i <= n; i++){
                result = Math.min(result, dp[i][i + n - ]);
            }
            System.out.println(result);
        }
    }
}