jhrsya

用户名：1564244868

访问量：13193

签　名：

等　　级
排　　名	644
经　　验	4066
参赛次数	2
文章发表	49
年　　龄	0
在职情况	学生
学　　校	南昌大学
专　　业

　　自我简介：

TA的其他文章

二叉树递归、非递归遍历算法，二叉树的创建，层次遍历算法，逆序层次遍历算法,高度计算递归及非递归算法
浏览：116

考研排序算法（快速排序，归并排序，堆排序）
浏览：172

你可能喜欢

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

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

动态规划问题，Bribe the Pri

　　作者: jhrsya　　　　发表时间：2020-02-04 22:17:54 浏览：232　|　评论：0　

![title](/image_editor_upload/20200204101640_18032.jpg)

![title](/image_editor_upload/20200204101721_74452.jpg)

#include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    #define INF (1 << 20)
    static const int MAX = 1000;
    int P,Q, a[MAX];  // A中保存输入数据，下标从1 开始
    int dp[MAX][MAX];  		//释放a[i]到a[j]囚犯的连续部分里的所有囚犯都释放，所需的最小金币总数
    
    void solve(){
    	a[0] = 0;
    	a[Q + 1] = P + 1;		//把左端当成0号囚犯，右端当成Q+1号囚犯，这样dp[0][Q]就是答案
    	
    	for(int q = 0; q <= Q; q++){
    		dp[q][q + 1] = 0;
    	} 
    	
    	//从短的区间开始天从Dp
    	 for(int w = 2; w <= Q + 1; w++){
    	 	for(int i = 0; i + w <= Q + 1; i++){
    	 		int j = i + w;
    	 		int t = INF;
    	 		//枚举最初释放的囚犯，计算最小的费用 
    	 		for(int k = i + 1; k < j; k++){
    	 			t = min(t, dp[i][k] + dp[k][j]);
    			 }
    			 //最初的释放还需要与释放无关的a[j] - a[i] - 2枚金币 
    			 dp[i][j] = t + a[j] - a[i] - 2;
    		 }
    	 }
    	 
    	 cout << dp[0][Q + 1] << endl;
    }
    int main()
    {
    	 cin >> P >> Q;
    	 for(int i = 1; i <= Q; i++){
    	 	cin >> a[i];
    	 }
    	 solve();
    	
        return 0;
    }

0.0分

1 人评分

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

jhrsya

TA的其他文章

你可能喜欢

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

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

【计算球体积】（C语言代码）

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

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

动态规划问题，Bribe the Pri

评论区

精彩推荐

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

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

C二级辅导-阶乘数列（C语言代码）

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

简单的a+b （C语言代码）

用筛法求之N内的素数。（C语言代码）

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

1048题解（读入回车问题）

排序算法（选择，插入，冒泡）

【计算球体积】（C语言代码）

jhrsya

TA的其他文章

你可能喜欢

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

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

【计算球体积】 （C语言代码）

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

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

动态规划问题，Bribe the Pri

评论区

精彩推荐

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

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

C二级辅导-阶乘数列 （C语言代码）

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

简单的a+b （C语言代码）

用筛法求之N内的素数。 （C语言代码）

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

1048题解（读入回车问题）

排序算法（选择，插入，冒泡）

【计算球体积】 （C语言代码）

【计算球体积】（C语言代码）

　　评论区

C二级辅导-阶乘数列（C语言代码）

用筛法求之N内的素数。（C语言代码）

【计算球体积】（C语言代码）