区间dp--NYOJ石子合并1

/*
    区间dp
    http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=737
    题意：n堆排列好的石子，两两结合，结合花费两堆石子之和
    问，最少的花费
    思路：区间dp，dp[i][j]表示i堆结合到j堆所用最少的花费
    三层循环，第一层控制宽度，即要求区间的范围
    第二层控制区间起始位置，第三层枚举区间的分割点 
*/
# include <iostream>
# include <algorithm>
# include <string.h>
# define INFI 0x3f3f3f3f
using namespace std;

int main(void)
{
//  freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n)
    {
        int num[205],dp[205][205],sum[205];
        memset(sum,0,sizeof(sum));
        memset(num,0,sizeof(num));
        for(int i=1; i<=n; ++i)
        {
            cin >> num[i];
            sum[i] = sum[i-1]+num[i];//前n项和 
        }

        for(int width=1; width<=n; ++width)
        {
            for(int i=1; i<=n-width; ++i)
            {
                int j = i + width;
                dp[i][j] = INFI;
                for(int k=i; k<j; ++k)
                {
                //  sum[j]-sum[i-1] 就是该区间的和
                // 因为最后两堆合并的时候，肯定就是该区间所有石子的和 
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
                }
            }
        }
        cout << dp[1][n]<<endl;
    }   
    return 0;
}

最后

以上就是美好泥猴桃为你收集整理的区间dp--NYOJ石子合并1的全部内容，希望文章能够帮你解决区间dp--NYOJ石子合并1所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。