青索

用户名：qingsuo123

访问量：538

签　名：

等　　级
排　　名	6504
经　　验	1354
参赛次数	2
文章发表	2
年　　龄	0
在职情况	学生
学　　校	洛阳师范学院
专　　业

　　自我简介：

TA的其他文章

动态规划（闫氏DP）合并石子
浏览：388

你可能喜欢

动态规划（闫氏DP）合并石子

　　作者: 青索　　　　发表时间：2022-04-07 21:20:46 浏览：388　|　评论：1　

原题链接：蓝桥杯算法提高VIP-合并石子

**思路：**石子合并到最后一定是左边一堆和右边一堆进行合并，所以当最后两堆石子花费都为最小时，合并成为的新一堆石子的花费也是最小的
所以状态转移方程：
**dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);**
dp[i][j]表示i到j堆石子合并的花费
s[n]表示前n堆石子的总和

难理解的可以搜一下闫氏DP
	#include<stdio.h>
    #include<string.h>
    int min(int a,int b)
    {
        if(a>=b)
            return b;
        else
            return a;
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        int s[n];
        memset(s,0,sizeof s);
        int dp[n+1][n+1];
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&s[i]);
            s[i]=s[i]+s[i-1];
        }
        memset(dp,0,sizeof dp);
        for(int len=2;len<=n;len++)//区间长度
        {
            for(int i=1;i+len-1<=n;i++)//区间起点
            {
                int j=i+len-1;
                dp[i][j]=0x3f3f3f3f;//赋值无穷大，方便比较
                for(int k=i;k<j;k++)//区间终点
                {
           dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
                }
            }
        }
        printf("%d",dp[1][n]);
    	return 0;
    }

0.0分

2 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

验题君

这个闫氏DP就狠6~

2022-04-12 08:23:02

青索

TA的其他文章

你可能喜欢

【蟠桃记】（C++代码）（递归计算）

C二级辅导-求偶数和（C语言代码）

输出九九乘法表（C语言代码）

Tom数（C++代码）

C语言训练-排序问题<1> （C++代码）

动态规划（闫氏DP）合并石子

评论区

精彩推荐

淘淘的名单（C语言代码）答案错误？？？

【出圈】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-字符串比较（C++代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

青索

TA的其他文章

你可能喜欢

【蟠桃记】 （C++代码）（递归计算）

C二级辅导-求偶数和 （C语言代码）

输出九九乘法表 （C语言代码）

Tom数 （C++代码）

C语言训练-排序问题<1> （C++代码）

动态规划（闫氏DP）合并石子

评论区

精彩推荐

淘淘的名单 （C语言代码）答案错误？？？

【出圈】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-字符串比较 （C++代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

字符逆序 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

【蟠桃记】（C++代码）（递归计算）

C二级辅导-求偶数和（C语言代码）

输出九九乘法表（C语言代码）

Tom数（C++代码）

　　评论区

淘淘的名单（C语言代码）答案错误？？？

【出圈】（C语言代码）

WU-字符串比较（C++代码）

字符逆序（C语言代码）