HzuQZH

用户名：h1810819001

访问量：32318

签　名：

等　　级
排　　名	45
经　　验	12276
参赛次数	7
文章发表	69
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

数据结构-KMP字符串模式匹配算法实现-题解(C++代码)
浏览：504

数据结构-用数组实现堆排（易处理，容易理解）
浏览：634

区间dp（动归思想）
浏览：938

你可能喜欢

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

区间dp（动归思想）

　　作者: HzuQZH　　　　发表时间：2019-08-06 10:10:06 浏览：938　|　评论：2　

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

```cpp
```cpp
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long LL;
typedef pair<int,int>Pall;
namespace IO{
    inline LL read(){
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;//不重要
const int N=1e3+7,INF=0x3f3f3f3f;
int dp[N][N],a[N],s[N];
//dp[i][j]表示从第i堆到第j堆的最小费用，s[i]表示前i堆的费用和
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        s[i]+=s[i-1]+a[i];//求前i块的代价（前缀和）
    }

for(int L=2;L<=n;L++){//枚举每次选的堆的长度，
        for(int i=1;i+L-1<=n;i++){//枚举在L长度下的i为起点
            int l=i,r=i+L-1;//l为i堆为起点时，r为L长度先i为起点的终点
            dp[l][r]=INF;//开始为正无穷
            for(int k=l;k<=r;k++){//枚举起点到终点的中间媒介
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);//从l到r可能是从l-k转移为l-r，s[r]-s[l-1]为这l-r的总费用(前缀和思想)
            }
        }
    }

printf("%d\n",dp[1][n]);
    return 0;
}
```

0.0分

9 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

wgy

不行啊，错误的答案拿出来

2020-02-27 19:01:03

18信二孙笑柯

然而还是超时了

2020-02-15 22:06:41

HzuQZH

TA的其他文章

你可能喜欢

求圆的面积（C语言代码）

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

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

蛇行矩阵（C语言代码）

C语言训练-邮票组合问题* （C语言代码）

区间dp（动归思想）

评论区

精彩推荐

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

聪明的美食家（C语言代码）

DNA （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

母牛的故事（C语言代码）

P1001 （C语言代码）

【排队买票】（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

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

HzuQZH

TA的其他文章

你可能喜欢

求圆的面积 （C语言代码）

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

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

蛇行矩阵 （C语言代码）

C语言训练-邮票组合问题* （C语言代码）

区间dp（动归思想）

评论区

精彩推荐

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

聪明的美食家 （C语言代码）

DNA （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

母牛的故事 （C语言代码）

P1001 （C语言代码）

【排队买票】 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

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

求圆的面积（C语言代码）

蛇行矩阵（C语言代码）

　　评论区

聪明的美食家（C语言代码）

母牛的故事（C语言代码）

【排队买票】（C语言代码）