acwing282.石子合并【区间dp】

acwing282.石子合并【区间dp】

acwing282.石子合并【区间dp】

#include "bits/stdc++.h"using namespace std;#define int long long#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n;int dp[305][305]; //记录区间最小int num[305]; //数列int pre[305]; //前缀和inline int sum(int l,int r){ //求区间和 return pre[r] - pre[l];}signed main(){ IOS memset(dp,0x3f,sizeof dp); cin>>n; for(int i = 1;i <= n;++i) cin>>num[i],pre[i] = pre[i - 1] + num[i],dp[i][i] = 0; for(int i = 2;i <= n;++i) //合并后的长度为2...n for(int l = 1,k = n - i + 1;l <= k;++l) //合并后起点为l，并且起点可以是1 ~ n-i+1 for(int p = l,r = l + i - 1;p < r;++p) dp[l][r] = min(dp[l][p] + dp[p + 1][r] + sum(l - 1,r),dp[l][r]); int ans = dp[1][n]; cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。