Comment

Huhu_Miao: 2025-05-18 20:09:36

/**
 *    author:  Huhu_Miao
 *    created: 2025.5.18 20:05:45 (UTC+8)
 *    e[i,j] : k_i ... k_j
 *    e[i , i-1]: 0
 *    e[i , j] = e[i, r-1] + e[r+1 , j] + w[i , j]
 *    w[i , j] =q_{i-1} + ... +pj + qj;
 *    e[i][i] = p_i + q_{i-1} + q_i;
**/
#include<iostream>
#include<iomanip>

constexpr int N = 501;
int k[N];
double p[N] , q[N], w[N][N], e[N][N];

void solve(){
    int n; std::cin >> n;
    for(int i = 1 ; i <= n ; i++) std::cin >> k[i];
    for(int i = 1 ; i <= n ; i++) std::cin >> p[i];
    for(int i = 0 ; i <= n ; i++) std::cin >> q[i];
    for(int i = 1 ; i <= n ; i++) w[i][i] = e[i][i] = p[i] + q[i-1] + q[i];
    for(int cnt = 2 ; cnt <= n ; cnt++){
        for(int i = 1 ; i <= n - cnt + 1 ;i++){
            int j = i + cnt - 1;
            w[i][j] = w[i][j-1] + p[j] + q[j];
        }
    }
    for(int cnt = 2 ; cnt <= n ; cnt++){
        for(int i = 1 ; i <= n - cnt + 1 ; i++){
            int j = i + cnt - 1;
            double min = 1e9;
            for(int r = i ; r<=j ; r++) min = std::min( min , e[i][r-1] + e[r+1][j] + w[i][j]);
            e[i][j] = min;
        }
    }
    std::cout << std::setprecision(6) <<std::fixed<< e[1][n] << '\n';
}

int main(){
    std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
    int T; std::cin>>T;
    while(T--) solve();
    return 0;
}

71123140焦博宇: 2025-05-15 11:38:10

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<climits>
#include<iomanip>
using namespace std;

double dp[505][505], p[505][505];
double _Cost[505], _cost[505];
int a;

int main()
{
	int M;
	cin >> M;
	for (int i = 1; i <= M; i++)
	{
		int N;
		cin >> N;
		for (int i = 1; i <= N; i++)
			cin >> a;
		for (int i = 1; i <= N; i++)
			cin >> _Cost[i];
		for (int i = 1; i <= N + 1; i++)
			cin >> _cost[i];
		memset(dp, 0, sizeof(dp));
		memset(p, 0, sizeof(p));
		for (int j = 0; j <= N - 1; j++)
			for (int i = 1; i <= N - j; i++)
			{
				if (j == 0)
					p[i][i + j] = _cost[i] + _cost[i + 1] + _Cost[i];
				else
					p[i][i + j] = p[i][i + j - 1] + _Cost[i + j] + _cost[i + j + 1];
			}
		for (int j = 0; j <= N - 1; j++)
			for (int i = 1; i <= N - j; i++)
			{
				dp[i][i + j] = INT_MAX;
				for (int k = i; k <= i + j; k++)
					dp[i][i + j] = min(dp[i][k - 1] + dp[k + 1][i + j] + p[i][i + j], dp[i][i + j]);
			}
		cout << fixed << setprecision(6) << dp[1][N] << endl;
	}
	return 0;
}

Westbrook: 2025-02-01 14:06:04

python会超时
N = 510
f = [[0]*N for i in range(N)]
w = [[0]*N for i in range(N)]
node = [0]*N
p = [0]*N
q = [0]*N
def min_tree(n,p,q,w):
    for len in range(1,n+1):
        for i in range(n-len+1):
            l,r = i,i+len
            w[i][r] = w[i][r - 1] + p[r] + q[r]
            f[l][r] = float('inf')
            for k in range(l+1,r+1):
                f[l][r] = min(f[l][r],f[l][k-1]+f[k][r])
            f[l][r] += w[l][r]
    return f[0][n]


if __name__ == '__main__':
    m = int(input())
    for i in range(m):
        n = int(input())
        node_tem = list(map(int,input().split()))
        p_tem = list(map(float,input().split()))
        for i in range(1,n+1):
            node[i] = node[i-1]
            p[i] = p_tem[i-1]
        q_tem = list(map(float,input().split()))
        for i in range(n+1):
            q[i] = q_tem[i]
        for i in range(n+1):
            w[i][i] = q[i]
        print('%.6f' % min_tree(n,p,q,w))

hanser414627925: 2024-05-29 15:24:35

#include<iostream>
#include<iomanip>
using namespace std;
#define INF 0x3f3f3f3f
void BST(double[], double[], int);
int key[500];
double p[501], q[501],c[501][501],w[501][501];
int main()
{
	int M, N;
	cin >> M;	//M<=10
	for (int i = 0; i < M; i++)
	{
		cin >> N;//表示N个关键字
		for (int j = 0; j < N; j++)
			cin >> key[j];//N个从小到大排好序的关键字
		for (int j = 1; j <= N; j++)
			cin >> p[j];//N个从小到大排好序的关键字
		for (int j = 0; j <= N; j++)
			cin >> q[j];//一行N+1个关键字外区间的搜索概率
		BST(p,q, N);
		cout << fixed<<setprecision(6)<<c[0][N] << endl;
	}
	return 0;
}
void BST(double p[], double q[], int n)
{
	for (int i = 0; i <= n; i++)
	{
		c[i][i] = 0;
		w[i][i] = q[i];
	}
	for (int x = 1; x <= n; x++)
		for (int i = 0; i <= n - x; i++)
		{
			int j = i + x;
			c[i][j] = INF;
			w[i][j] = w[i][j - 1] + p[j] + q[j];
			for (int k = i+1; k <= j; k++)
			{
				double t = w[i][j] + c[k][j]+ c[i][k - 1];
				if (t < c[i][j])c[i][j] = t;
			}
		}
}

iridescent: 2024-05-24 11:07:28

直接按照书上算完减去所有关键字外的概率和就可以了，书上算出2.1,2.1-0.2-0.2-0.2就是答案1.5

Teriqma: 2023-06-12 21:17:34

改成double就对了qwq

lin zehao: 2023-05-11 19:36:04

也可以在最开始就将叶节点（E[i][i-1]）设为0而非q_(i-1)，初始化时就不算叶子本身的代价。

LeonWong: 2021-11-11 17:57:00

感谢三楼老哥。

算法学习1号机: 2021-11-01 10:09:36

和合并石子类似的区间DP题目，根据整棵树的根来枚举，左子树，根，右子树（假定左右子树已经是最优二叉树）。

LMxKc1998831: 2020-12-24 21:38:55

这题的代价不太一样，关键字之外区间的搜索代价也为该区间到树的根的路径上关键字节点的个数，比书上说的代价少1，其实可以直接按照书上算完减去所有关键字外的概率和

pinkpig: 2020-12-15 16:41:07

结果错的话试试把float换成double

201956 孙域: 2020-10-23 10:00:36

这题按照算法导论的方法做 做出2.1 2.2