算法提高 合并石子

问题描述
  在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
输入格式
  输入第一行包含一个整数n,表示石子的堆数。
  接下来一行,包含n个整数,按顺序给出每堆石子的大小 。
输出格式
  输出一个整数,表示合并的最小花费。
样例输入
5
1 2 3 4 5
样例输出
33
数据规模和约定
  1<=n<=1000, 每堆石子至少1颗,最多10000颗。
 
动态规划,记录每1,2,3,4....合并最小(一堆费用是0,两堆合并就是两个数相加,三堆是先合并前两堆,或者先合并后两堆,哪两堆的和小,就合并哪两堆,最后一次合并都是三堆的总和,差距在第一次合并,因此合并第i ~ j堆的最小费用应该是划分成两堆,找到两堆费用和最小,再加上i~j堆的和,就是合并的总费用(每次合并两堆))。
 dp代码:
#include <cstdio>
#include <cstring>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;

int n,temp;
int dp[1001][1001],s[1001];

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&s[i]);
        s[i] += s[i - 1];
    }
    for(int h = 1;h <= n - 1;h ++)
    {
        for(int i = 1;h + i <= n;i ++)
        {
            int j = i + h;
            dp[i][j] = inf;
            for(int k = i;k < j;k ++)
            {
                temp = dp[i][k] + dp[k + 1][j];
                if(dp[i][j] > temp)dp[i][j] = temp;///用min函数会超时。。
            }
            dp[i][j] += s[j] - s[i - 1];
        }
    }
    printf("%d",dp[1][n]);
}
View Code

递归记忆化(末点超时):

#include <cstdio>
#include <cstring>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;

int n;
int dp[1001][1001],s[1001];
inline int get(int x,int y)
{
    if(x == y || dp[x][y])return dp[x][y];
    int mi = inf;
    for(int k = x;k < y;k ++)
    {
        int temp = get(x,k) + get(k + 1,y);
        if(mi > temp)mi = temp;
    }
    return dp[x][y] = mi + s[y] - s[x - 1];
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&s[i]);
        s[i] += s[i - 1];
    }
    printf("%d",get(1,n));
}
View Code
原文地址:https://www.cnblogs.com/8023spz/p/9074439.html