codevs 1090 加分二叉树

一道树型dp,方程在程序里有,注意循环的顺序和初始化。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long dp[35][35],n,w[35],c[35][35];
void find(long long left,long long right)
{
if (left>right) return;
printf("%d ",c[left][right]);
if (left!=right)
{
find(left,c[left][right]-1);
find(c[left][right]+1,right);
}
return;
}
int main()
{
memset(dp,0,sizeof(dp));
memset(c,0,sizeof(c));
scanf("%lld",&n);
for (long long i=1;i<=n;i++)
scanf("%lld",&w[i]);
for (long long i=1;i<=n;i++)
{
dp[i][i]=w[i];
dp[i][i-1]=1;
c[i][i]=i;
}
for (long long j=1;j<=n;j++)
for (long long i=j-1;i>=1;i--)
for (int k=i;k<=j;k++)
{
if (dp[i][j]<dp[i][k-1]*dp[k+1][j]+w[k])
{
dp[i][j]=dp[i][k-1]*dp[k+1][j]+w[k];
c[i][j]=k;
}
}
printf("%lld\n",dp[1][n]);
find(1,n);
return 0;
}

时间: 02-08

codevs 1090 加分二叉树的相关文章

1090 加分二叉树

1090 加分二叉树 2003年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题解 题目描述 Description 设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号.每个节点都有一个分数(均为正整数),记第j个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree

NOIP2003 加分二叉树

题三    加分二叉树 [问题描述] 设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号.每个节点都有一个分数(均为正整数),记第j个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数 若某个子树为主,规定其加分为1,叶子的加分就是叶节点本身的分数.不考虑它的空 子树. 试求一棵符合中序遍

NOIP2003加分二叉树[树 区间DP]

题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号.每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数. 若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数.不考虑它的空子树. 试求一棵符合中序遍历为(1,2,3,…,n)且

【洛谷】P1040 加分二叉树

[洛谷]P1040 加分二叉树 题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,-,n),其中数字1,2,3,-,n为节点编号.每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数. 若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数.不考虑它的空子树. 试求一棵符合中

NOIP2003TG 加分二叉树 区间DP

加分二叉树 (binary) [问题描述] 设一个 n 个节点的二叉树 tree 的中序遍历为( l,2,3,…,n ),其中数字 1,2,3,…,n 为节点编号.每个节点都有一个分数(均为正整数),记第 j 个节点的分数为 di , tree 及它的每个子树都有一个加分,任一棵子树 subtree (也包含 tree 本身)的加分计算方法如下: subtree 的左子树的加分 × subtree 的右子树的加分+ subtree 的根的分数 若某个子树为空,规定其加分为 1 ,叶子的加分就是叶

P1040 加分二叉树

转自:(http://www.cnblogs.com/geek-007/p/7197439.html) 经典例题:加分二叉树(Luogu 1040) 设一个 n 个节点的二叉树 tree 的中序遍历为( 1,2,3,…,n),其中数字 1,2,3,…,n 为节点编号.每个节点都有一个分数(均为正整数),记第 i 个节点的分数为 di, tree 及它的每个子树都有一个加分,任一棵子树 subtree(也包含 tree 本身)的加分计算方法如下: subtree 的左子树的加分 × subtree

【luogu1040】加分二叉树

题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,-,n),其中数字1,2,3,-,n为节点编号.每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数. 若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数.不考虑它的空子树. 试求一棵符合中序遍历为(1,2,3,-,n)且

[NOIP2003] 提高组 洛谷P1040 加分二叉树

题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号.每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数. 若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数.不考虑它的空子树. 试求一棵符合中序遍历为(1,2,3,…,n)且

洛谷 P1040 加分二叉树

题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号.每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数. 若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数.不考虑它的空子树. 试求一棵符合中序遍历为(1,2,3,…,n)且