网站添加白名单,哪些网站教你做美食的,网站制作地点,成都设计公司排名前十强石子合并
设有 N 堆石子排成一排#xff0c;其编号为 1,2,3,…,N。
每堆石子有一定的质量#xff0c;可以用一个整数来描述#xff0c;现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆#xff0c;合并的代价为这两堆石子的质量之和#xff0c;合并后与这两堆…石子合并
设有 N 堆石子排成一排其编号为 1,2,3,…,N。
每堆石子有一定的质量可以用一个整数来描述现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻合并时由于选择的顺序不同合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2 我们可以先合并 1、2堆代价为 4得到 4 5 2 又合并 1、2堆代价为 9得到 9 2 再合并得到 11总代价为 491124
如果第二步是先合并 2、3堆则代价为 7得到 4 7最后一次合并代价为 11总代价为 471122。
问题是找出一种合理的方法使总的代价最小输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数表示最小代价。
数据范围
1≤N≤300
输入样例
4
1 3 5 2输出样例
22 每个状态只会依赖比它长度更短的其他状态所以先枚举长度可以保证在计算每个状态之前先计算出它所依赖的状态。
如果先枚举 i 可以知道 起点小于 i 的所有情况 起点为i长度小于 len的所有情况 不能知道 起点大于i 的所有情况 起点为i长度大于 len的情况
如果先枚举 len 可以知道 长度小于 len的所有情况 长度为 len起点小于 i 的所有情况 不能知道 长度大于 len的所有情况 长度为 len起点大于 i 的情况
需求
f[i][k] 起点为 i长度为 k - i 1 len 两种都可以
f[k1][j] 起点为 k 1 i长度为 j - k len 不能先枚举 i #includeiostream
#includecstring
using namespace std;
const int N330;
int f[N][N];//f[i][j]表示第i堆石子到第j堆石子一段区间合并成一堆需要的最小代价
int w[N],s[N];
int main()
{int n;cinn;for(int i1;in;i)cinw[i];memset(f,0x3f,sizeof f);//求最小值 故需要初始化最大for(int i0;in;i) f[i][i]0;//i到i只有自己 不需要花费 for(int i1;in;i) s[i]s[i-1]w[i];//前缀和for(int len2;lenn;len){for(int i1;ilen-1n;i)//枚举长度{int li,rilen-1;//区间的左端点 右端点for(int k1;kr;k){//计算i到j 合并成一堆 最后肯定是 在l--r区间中一个分界线合成一堆 //先不求最后那一和 合成左堆最小代价 f[l][k] 合成右堆的最小代价 f[k1][r]//最后一步将左右两堆合起来 左堆的最小代价右堆的最小代价合成最后一步就是l-r的代价f[l][r]min(f[l][r],f[l][k]f[k1][r]s[r]-s[l-1]);}}}coutf[1][n]endl;//输出从第一堆石子到第n堆石子合并为一堆石子的最小代价return 0;
} 合并果子贪心 Huffman树
在一个果园里达达已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。
达达决定把所有的果子合成一堆。
每一次合并达达可以把两堆果子(任意两堆不受限制合并到一起消耗的体力等于两堆果子的重量之和。
可以看出所有的果子经过 n−1 次合并之后就只剩下一堆了。
达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家所以达达在合并果子时要尽可能地节省体力。
假定每个果子重量都为 1并且已知果子的种类数和每种果子的数目你的任务是设计出合并的次序方案使达达耗费的体力最少并输出这个最小的体力耗费值。
例如有 3 种果子数目依次为 129。
可以先将 1、2堆合并新堆数目为 3耗费体力为 3。
接着将新堆与原先的第三堆合并又得到新的堆数目为 12耗费体力为 12。
所以达达总共耗费体力31215。
可以证明 15 为最小的体力耗费值。
输入格式
输入包括两行第一行是一个整数 n表示果子的种类数。
第二行包含 n 个整数用空格分隔第 i 个整数 ai 是第 i 种果子的数目。
输出格式
输出包括一行这一行只包含一个整数也就是最小的体力耗费值。
输入数据保证这个值小于 231。
数据范围
1≤n≤10000 1≤ai≤20000
输入样例
3
1 2 9 输出样例
15
经典的Huffman树 每次合并重量最小的两堆果子即可 #includeiostream
#includealgorithm
#includequeue
using namespace std;
int main()
{priority_queueint,vectorint,greaterintheap;int n;cinn;for(int i1;in;i){int a;cina;heap.push(a);}int ans0;while(heap.size()1){int x1heap.top();heap.pop();int x2heap.top();heap.pop();ansx1x2;heap.push(x1x2);}coutansendl;return 0;
} 环形石子合并
将 n 堆石子绕圆形操场排放现要将石子有序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆并将新的一堆的石子数记做该次合并的得分。
请编写一个程序读入堆数 n 及每堆的石子数并进行如下计算
选择一种合并石子的方案使得做 n−1次合并得分总和最大。选择一种合并石子的方案使得做 n−1 次合并得分总和最小。
输入格式
第一行包含整数 n表示共有 n 堆石子。
第二行包含 n 个整数分别表示每堆石子的数量。
输出格式
输出共两行
第一行为合并得分总和最小值
第二行为合并得分总和最大值。
数据范围
1≤n≤200
输入样例
4
4 5 9 4输出样例
43
54 #includeiostream
#includealgorithm
#includecstring
using namespace std;
const int N440;
int f[N][N],g[N][N];
int w[N],s[N];
int main()
{int n;cinn;for(int i1;in;i){cinw[i];w[in]w[i];}for(int i1;i2*n;i) s[i]s[i-1]w[i];memset(f,0x3f,sizeof f);//求最小值 故初始化成大的memset(g,-0x3f,sizeof g);//求最大值 故初始化成小的for(int len1;lenn;len){for(int i1;ilen-12*n;i){int li,rilen-1;if(lr){f[l][r]0,g[l][r]0;//只有自己一堆的时候 不需要花费}for(int kl;kr;k){f[l][r]min(f[l][r],f[l][k]f[k1][r]s[r]-s[l-1]);g[l][r]max(g[l][r],g[l][k]g[k1][r]s[r]-s[l-1]);}}}int min10x3f3f3f3f,max1-0x3f3f3f3f;for(int i1;in;i){min1min(min1,f[i][in-1]);max1max(max1,g[i][in-1]);}coutmin1endlmax1endl;return 0;
}
