NYOJ 737 石子合并(一)(环形)

2024-09-07 03:38
文章标签 合并 nyoj 环形 石子 737

本文主要是介绍NYOJ 737 石子合并(一)(环形),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

OJ题目:http://acm.nyist.net/JudgeOnline/problem.php?pid=737

参考资料:http://wenku.baidu.com/view/b4dbe923482fb4daa58d4b84.html (感觉解释的很好)

描述
    有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。
输入
有多组测试数据,输入到文件结束。
每组测试数据第一行有一个整数n,表示有n堆石子。
接下来的一行有n(0< n <200)个数,分别表示这n堆石子的数目,用空格隔开
输出
输出总代价的最小值,占单独的一行
样例输入
3
1 2 3
7
13 7 8 16 21 4 18
样例输出
9
239
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <set>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define SWAP(a , b){ int temp = a; a = b; b = temp;}
#define inf 100000000using namespace std;
typedef long long LL;int main()
{int n;int x[202];int dpmin[202][202];int sum[202][202];while(cin >> n){memset(x , 0 , sizeof(x));for(int i = 1;i <= n;i++){scanf("%d",&x[i]);}for(int i = 1;i <= n;i++){sum[i][i] = x[i];for(int j = i + 1;j <= n;j++){sum[i][j] = sum[i][j - 1] + x[j];}}for(int len = 2;len <= n;len++){for(int i = 1;i <= (n-len+1);i++){int j = i + len - 1;dpmin[i][j] = inf;for(int k = i;k <= j - 1;k++){dpmin[i][j] = Min(dpmin[i][j] , dpmin[i][k] + dpmin[k + 1][j] + sum[i][j]);}}}cout << dpmin[1][n] <<endl;}return 0;
}

这篇关于NYOJ 737 石子合并(一)(环形)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1143953

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

【Python从入门到进阶】64、Pandas如何实现数据的Concat合并

接上篇《63.Pandas如何实现数据的Merge》 上一篇我们学习了Pandas如何实现数据的Merge,本篇我们来继续学习Pandas如何实现数据的Concat合并。 一、引言 在数据处理过程中,经常需要将多个数据集合并为一个统一的数据集,以便进行进一步的分析或建模。这种需求在多种场景下都非常常见,比如合并不同来源的数据集以获取更全面的信息、将时间序列数据按时间顺序拼接起来以观察长期趋势等

nyoj 288 士兵杀敌(五)

一道插线问线离线版的题  复杂度O(n); 代码如下: #include<stdio.h>#include<string.h>const int M = 1000003;const int mod=10003;int num[M];int main(){int n,c,q;scanf("%d%d%d",&n,&c,&q);while(c--){int a,b,x;scan

nyoj 1037 Postscript of Tian Ji racing

一道卡贪心的题。 也算一道改编题。 此题的解法推荐为二分图的最大匹配。 首先将输入数据转换一下,然后将满足题意的一组牌建立条边,最终边的覆盖数即为 LN 最后可得的分数。 然后求出最大匹配即可。 代码如下: #include<stdio.h>#include<string.h>char card[30][5];char s[5];int map[30][30];

nyoj 1002 Trucking

同样一道改编题。 只要把题意理解了好。 简单的二分加最短路。 只要二分高度, 然后求最短路,输出满足题意的即可。 代码如下: (最短路用spfa 时间效率高) #include <iostream>#include <cstdio>#include <cstring>#include <ctime>#include <queue>using namespace st

nyoj 1072 我想回家

一道相当题目描述相当扯的题。 这道题目的描述最后说的是求出到达最后一个点的最短距离,所以输入数据最后输入的城堡的坐标是没用的。 就是先求出两点之间的距离,若不大于村落间距离,并且不大于最后的距离限制 l ,则在两点间建边。 最后任意方法求出最短路即可。 #include <iostream>#include<stdio.h>#include<vector>#include<

nyoj 1038 纸牌游戏

poj 的一道改编题,说是翻译题更恰当,因为只是小幅度改动。 一道模拟题,代码掌控能力比较好,思维逻辑清晰的话就能AC。 代码如下: #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct node{char c[5];int rk;char da[5];int nu

nyoj 685 查找字符串

当初一开始没做出来。 后来,学习过一段时间之后,在返回来做这道题,忽然发现,map类容器可以做。 PS:需要注意的是:此题如果用c++的输入输出的话,会超时。 O(time):gets()<  scanf() < cin。   附上代码: #include<stdio.h>#include<map>#include<string>#include<string.h>usin