动态规划之石子合并问题

Bertha 。 2022-04-22 02:14 179阅读 0赞

\#include <iostream>

using namespace std;

\#define LEN 1024  
\#define MAXDATA 200000  
int MIN\[LEN\]\[LEN\];//最小得分  
int MAX\[LEN\]\[LEN\];//最大得分  
int data\[LEN\];//初始每堆石子数  
int sum\[LEN\];//0-LEN石子堆数

int min(int a, int b)  
\{  
    return a > b? b : a;  
\}

int max(int a, int b)  
\{  
    return a > b ? a : b;  
\}

void straight(int len)  
\{  
    //初始化对角线  
    for (int i = 1; i <= len; ++i)  
    \{  
        MIN\[i\]\[i\] = 0;  
        MAX\[i\]\[i\] = 0;  
    \}  
    sum\[0\] = 0;  
    sum\[1\] = data\[1\];  
    for (int i = 1; i < len; ++i)  
    \{  
        sum\[i + 1\] = sum\[i\] + data\[i + 1\];  
    \}  
    for (int i = 0; i <= len; ++i)  
    \{  
        std::cout << sum\[i\] << "\\t";  
    \}  
    //数据坐标分析  
    for (int v = 2; v <= len; ++v)  
    \{  
        for (int i = 1; i <= len - v + 1; ++i)  
        \{  
            int j = i + v - 1;  
            MIN\[i\]\[j\] = MAXDATA;  
            MAX\[i\]\[j\] = -1;  
            int temp = sum\[j\] - sum\[i - 1\];  
            for (int k = i; k < j; ++k)  
            \{  
                MIN\[i\]\[j\] = min(MIN\[i\]\[j\], MIN\[i\]\[k\] + MIN\[k + 1\]\[j\] + temp);  
                MAX\[i\]\[j\] = max(MAX\[i\]\[j\], MAX\[i\]\[k\] + MAX\[k + 1\]\[j\] + temp);  
            \}  
        \}  
    \}  
\}  
int main()  
\{  
    int all;  
    std::cout << "请输入有多少堆石子" << std::endl;  
    std::cin >> all;  
    std::cout << "请分别输入每堆石子的个数" << std::endl;  
    for (int i = 1; i <= all; ++i)  
    \{  
        std::cin >> data\[i\];  
    \}  
    straight(all);  
    std::cout << "\\n";  
    std::cout << "最小花费是" << MIN\[1\]\[all\] << std::endl;  
    std::cout << "最大花费是" << MAX\[1\]\[all\] << std::endl;  
    return 0;  
\}