株洲做网站 省心磐石网络,用户体验好网站,敖汉旗网站建设,做网站软件大全石子合并#xff08;弱化版#xff09;
题目描述
设有 N ( N ≤ 300 ) N(N \le 300) N(N≤300) 堆石子排成一排#xff0c;其编号为 1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N 1,2,3,⋯,N。每堆石子有一定的质量 m i ( m i ≤ 1000 ) m_i\ (m_i \le 1000) mi (mi≤1000)。…石子合并弱化版
题目描述
设有 N ( N ≤ 300 ) N(N \le 300) N(N≤300) 堆石子排成一排其编号为 1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N 1,2,3,⋯,N。每堆石子有一定的质量 m i ( m i ≤ 1000 ) m_i\ (m_i \le 1000) mi (mi≤1000)。现在要将这 N N N 堆石子合并成为一堆。每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同合并的总代价也不相同。试找出一种合理的方法使总的代价最小并输出最小代价。
输入格式
第一行一个整数 N N N。
第二行 N N N 个整数 m i m_i mi。
输出格式
输出文件仅一个整数也就是最小代价。
样例 #1
样例输入 #1
4
2 5 3 1样例输出 #1
22区间动态规划 令 d p [ i ] [ j ] dp[i][j] dp[i][j]表示区间 [ i , j [i,j [i,j]的最小价值。 不妨从终点考虑问题即结果为两个子区间合并的最小值再加上合并需要的代价即可。 枚举两个子区间即枚举这个区间的中间点k使这个区间被分为 [ i , k ] [i,k] [i,k]和 [ k 1 , j ] [k1,j] [k1,j]两个区间取一遍最小值加上合并的价值 w [ i ] [ j ] w[i][j] w[i][j]即为当前区间所求。 至于合并的代价用前缀和即可。
得出方程 d p [ i ] [ j ] m i n ( d p [ i ] [ j ] , d p [ i ] [ k ] d p [ k 1 ] [ j ] s u m [ j ] − s u m [ i − 1 ] ) dp[i][j]min(dp[i][j],dp[i][k]dp[k1][j]sum[j]-sum[i-1]) dp[i][j]min(dp[i][j],dp[i][k]dp[k1][j]sum[j]−sum[i−1])
AC CODE
#includebits/stdc.h
using namespace std;
const int N1e51145;
const int INF0x7f7f7f7f;
int n,a[N],sum[N],f[2000][2000];
int main(){cinn;for(int i1;in;i){cina[i];f[i][i]0;sum[i]sum[i-1]a[i];}for(int len2;lenn;len){for(int l1;ln-len1;l){int rllen-1;f[l][r]INF;for(int kl;kr;k){f[l][r]min(f[l][r],f[l][k]f[k1][r]sum[r]-sum[l-1]);}}}coutf[1][n];return 0;
}附封面
