- 浏览: 105940 次
- 性别:
- 来自: 广州
最新评论
-
xinhemei:
我试了试,发现gmail和163的不行。好像ajax请求失败了 ...
jQuery实现邮箱自动登录 -
酒鬼_yuan:
我正在找 谢谢了
关于yui的学习
我们学校的oj的
#include <stdio.h> #include <memory.h> int sum[105][105] = {0};//合并后的状态分 int dp[105][105] = {0};//见下面注释 int p[105] = {0}; int n; int dpMax(int start, int length) { int k, temp = 0; if (dp[start][length] != -1) { return dp[start][length]; //已经求过 } dp[start][length] = 0; //枚举划分的情况 for (k = 1; k <= length - 1; k++) { temp = dpMax(start, k) + dpMax((start + k - 1) % n + 1, length - k) + sum[start][length]; if (temp > dp[start][length]) { dp[start][length] = temp; } } return dp[start][length]; } int dpMin(int start, int length) { int k, temp = 0; if (dp[start][length] != -1) { return dp[start][length]; //已经求过 } dp[start][length] = 32767; if (length == 1) { dp[start][length] = 0; } //枚举划分的情况 for (k = 1; k <= length - 1; k++) { temp = dpMin(start, k) + dpMin((start + k - 1) % n + 1, length - k) + sum[start][length]; if (temp < dp[start][length]) { dp[start][length] = temp; } } return dp[start][length]; } /* * 动态规划经典问题 石子合并 * 感谢黄大牛!!! * 在一个圆形操场的四周摆放着n 堆石子。 * 现要将石子有次序地合并成一堆。 * 规定每次只能选相邻的2 堆石子合并成新的一堆, * 并将新的一堆石子数记为该次合并的得分。 * 试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 * input * 4 * 4 4 5 9 * output * 43 * 54 * * 设dp[i][k]表示以i为起点,长度为k的直线上各堆石子的最优合并状态 * sum[i][k]表示以i为起点,长度为k的直线上各堆石子的总分 * 枚举起点,变环为直线 * * 对于每一条长度为k的直线有k-1种划分方法, * 枚举后,就求出最优值 * 如:4 4 5 9,看成已经合并后的一个大堆,共有3种划分,即 * 4 459;44 59;445 9;看成是这三种情况下每两个堆的合并 * dp[1][4]=dp[1][1]+dp[2][3]+sum[1][4] * =dp[1][2]+dp[3][2]+sum[1][4] * =dp[1][3]+dp[4][1]+sum[1][4] * 子问题再类似分解 * dp[2][3]=dp[2][1]+dp[3][2]+sum[2][3] * =dp[2][2]+dp[][]+sum[2][3] * dp[2][2]=dp[2][1]+dp[3][1]+sum[2][2] * dp[1][2]=dp[1][1]+dp[2][1]+sum[1][2] * dp[3][2]=dp[3][1]+dp[4][1]+sum[3][2] * dp[1][3]=dp[1][1]+dp[2][2]+sum[1][3] * =dp[1][2]+dp[3][1]+sum[1][3] * 而dp[1][1]=4;dp[2][1]=4;dp[3][1]=5;dp[4][1]=9; * 从上递归或从下递推都能求得最优值 * 也就是要把dp[][]和sum[][]这两张表填写完毕 * 按照假设,这两张表要按列来填 */ int main() { int i, j, max = 0, min = 32767, temp = 0; scanf("%d", &n); //输入 for (i = 1; i <= n; i++) { scanf("%d", & p[i]); } memset(sum, 0, sizeof (sum)); //填求和的表,按列填 //第一列 for (i = 1; i <= n; i++) { sum[i][1] = p[i]; } //余下的 for (j = 2; j <= n; j++) { for (i = 1; i <= n; i++) { sum[i][j] = sum[i % n + 1][j - 1] + sum[i][1]; // } } // memset(dp, -1, sizeof (dp)); //枚举起点,变环为线 for (i = 1; i <= n; i++) { temp = dpMin(i, n); if (temp < min) { min = temp; } } memset(dp, -1, sizeof (dp)); //枚举起点,变环为线 for (i = 1; i <= n; i++) { temp = dpMax(i, n); if (temp > max) { max = temp; } } printf("%d\n", min); // for(i=1;i<=n;i++){ // for(int j=1;j<=n;j++){ // printf("%d ",sum[i][j]); // } // printf("\n"); // } printf("%d\n", max); return 1; }
发表评论
-
Poj3126
2010-05-29 22:07 1199import java.io.BufferedIn ... -
poj3125简单模拟
2010-05-25 11:44 919import java.io.BufferedInputS ... -
还是水
2010-05-24 12:53 730import java.io.BufferedInputS ... -
Poj3085再水一下
2010-05-24 12:28 824import java.io.BufferedInputS ... -
Poj3673超水题
2010-05-24 12:12 817package easy; import java. ... -
Poj3278 广度优先搜索
2010-05-22 23:24 1285import java.io.BufferedInputS ... -
合唱队形
2010-05-09 21:45 2102#include <stdio.h> #incl ... -
poj3199 高精
2010-05-09 21:44 923import java.io.BufferedInputS ... -
poj1002 郁闷的电话号码
2010-05-08 23:48 1227import java.io.BufferedInputS ... -
poj1298 无语。。。
2010-04-24 23:24 973import java.io.BufferedInputStr ... -
poj1017 装箱问题 简单贪心
2010-04-18 16:56 2322import java.io.BufferedInpu ... -
poj1042 枚举+贪心算法
2010-04-18 00:45 1762import java.io.BufferedInputS ... -
zoj3197 Google Book 贪心算法
2010-04-15 23:54 1339#include <stdio.h> #defi ... -
Poj2453 an easy program
2010-04-09 00:19 830/* * To change this template, ... -
poj2299 递归与分治策略
2010-04-02 23:38 1397package hard; import java.io ... -
poj1723 数学问题
2010-04-02 15:31 989package middle; import jav ... -
Poj2524 并查集
2010-03-18 15:22 838package middle; import jav ... -
Poj1308 并查集
2010-03-18 15:21 1660package middle; import jav ... -
poj1405 高精
2010-02-28 11:09 1333import java.io.BufferedInputS ... -
poj1979 深度遍历
2010-02-27 20:56 1258问题重述 问题描述: ...
相关推荐
解题思路:类似于矩阵连乘问题,可以用动态规划的方法来解决: (1)定义一个n*n的数组A来存储合并石子的最小合并方式,由一开始的只有两堆石子要合并慢慢向上递归得到n堆石子合并的最小得分。 (2)定义另一个...
动态规划 解决石子合并问题 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只 能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出...
针对石子合并问题,本文利用动态规划算法寻求石子合并时的最大,最小得分,选择相邻的两堆石子堆进行合并,其最终花费的代价与石子堆的排列顺序有关。根据其重叠子问题建立状态转移方程,利用程序进行求解。算例结果...
用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题
动态规划解石子合并问题,其中石子呈环形排列。源程序为c++代码。
用动态规划方法解决石子合并问题,很不错的一个算法!嘿嘿......
第一个石子合并模型,和书上3.1节的矩阵连乘问题类似. 假设m[i,j]为合并石子ai…aj, 1≤i≤j≤n,所得到的最小得分,若没有“合并”这个动作,则为0。原问题所求的合并最小值即为m[1,n]。 递推公式如下,其中min表示...
在一个圆形操场的四周摆放着n 堆石子。...规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。源代码
9动态规划算法2-石子合并.doc
Problem D:石子合并(包含源程序c++) Time Limit:1000MS Memory Limit:65536K Description 在一个圆形操场的四周摆放着 n 堆石子. 现要将石子有次序地合并成一堆, 规定每次只能选相邻的 2 堆石子合并成新的一堆, ...
11079 可以移动的石子合并 时间限制:1000MS 内存限制:1000K 提交次数:0 通过次数:0 题型: 编程题 语言: 无限制 Description 有n堆石子形成一行(a1,a2,…,an,ai为第i堆石子个数),现要将石子合并成一堆,规定...
算法分析课程作业,C语言编写,可能需要用input.txt输入,石子合并问题代码
规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务: 对于给定n堆石子,编程计算合并成一堆的最小...
算法实现题3-6 石子合并问题 «问题描述: 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只 能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一 个...
规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务: 对于给定n堆石子,编程计算合并成一堆的最小...
在空地上,有n堆石子排成一排,你需要把这些石子合并成一堆石子。你每次只能合并 相邻的两堆石子。而将两堆石子合并的代价是这两堆石子的个数之和。 在开始合并前,你可以有一次机会去交换某相邻的两堆石子。
C语言实现的石子合并问题,自己可以改成其他的语言,这是核心语句
动态规划典型题目:在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成...
规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务: 对于给定n堆石子,编程计算合并成一堆的最小...