想找公司做网站,西昌市做网站的,晏阳初乡村建设网站,企业管理咨询收费方案明细P1651 塔 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
小明很喜欢摆积木#xff0c;现在他正在玩的积木是由 N 个木块组成的#xff0c;他想用这些木块搭出两座高度相同的塔#xff0c;一座塔的高度是搭建它的所有木块的高度和#xff0c;并且一座塔至少要用…P1651 塔 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
小明很喜欢摆积木现在他正在玩的积木是由 N 个木块组成的他想用这些木块搭出两座高度相同的塔一座塔的高度是搭建它的所有木块的高度和并且一座塔至少要用一个木块。每个木块只能用一次也可以不用。目前已知每块木块的高度小明想知道在最终两个塔的高度相同的情况下他所能搭的塔的最大高度是多少你能帮助他吗
输入格式
第一行为一个整数 N表示木块个数。
第二行是 N 个整数表示 N 块木块的高度。
输出格式
仅一个整数表示能搭建的塔的最大高度若不能搭建两座相同高度的塔则输出 -1。
输入输出样例
输入 #1复制
3
2 3 5
输出 #1复制
5
说明/提示
对于 100% 的数据N≤50 每块木块的高度 ℎ 满足 1≤h≤500000所有木块的高度总和 ≤500000。
解析 1. 思考解法 文本串后面的内容不会影响文本串前半部分的最优解符合无后效性。实际上有后效性也可以只不过很复杂 若把文本串右端位置作为状态文本串右端位置较靠右的状态需要通过文本串右端位置较靠左的状态得到如 di 需要通过 d0…di−1 的其中之一得到符合子问题重叠性。 集合划分f[i][j]:表示前 i 个积木可以搭成得两个高度差为 j 得塔得最高塔得高度 该状态可由以下四种状态转移而来 不选第 i 个积木f[i-1][j] 将第 i 个积木放在最矮的塔上f[i-1][ja[i]]; 将第 i 个积木放在最高的塔上f[i-1][j-a[i]]a[i]; 将第 i 个积木放在最矮的塔上然后最矮的塔变成最高的塔f[i-1][a[i]-j]j;
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
using namespace std;
typedef long long LL;
const int N 55,M5e55;
int n;
int a[N], f[N][M];int main() {int sum 0;scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);sum a[i];}memset(f, -1, sizeof(f));f[0][0] 0;for (int i 1; i n; i) {for (int j 0; j sum; j) {f[i][j] max(f[i - 1][j], f[i - 1][j a[i]]);if (j a[i])f[i][j] max(f[i - 1][j - a[i]] a[i], f[i][j]);if(j a[i])f[i][j] max(f[i - 1][a[i] - j] j, f[i][j]);}}if (f[n][0] 0)cout -1 endl;elsecout f[n][0] endl;return 0;
}
