SDNU 1045.石子合并1（区间dp）

Description

有n堆石子排成一行，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。

Input

第一行一个整数n(1 <= n <= 200)，表示石子堆数； 第二行n个整数a(1 <= a <= 100)，表示每堆石子的个数。

Output

一个整数，表示最小总得分。

Sample Input

5 7 6 5 7 100

Sample Output

175

Source

Unknown 思路：

 

 

#include<bits/stdc++.h> using namespace std; #define ll long long #define eps 1e-9 #define pi acos(-1) const int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int maxn = 1000 + 8; int n, a[maxn], sum[maxn], dp[maxn][maxn]; int main() { std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); sum[0] = 0; while(cin >> n) { memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) { cin >> a[i]; sum[i] += a[i] + sum[i - 1]; } for(int i = 1; i <= n; i++) { for(int j = 1; j + i <= n; j++) { int en = j + i; int tmp = sum[en] - sum[j - 1]; dp[j][en] = inf; for(int k = j; k < en; k++) dp[j][en] = min(dp[j][en], dp[j][k] + dp[k + 1][en] + tmp); } } cout << dp[1][n] <<'\n'; } return 0; }

 

转载于:https://www.cnblogs.com/RootVount/p/11480385.html

相关资源：JAVA上百实例源码以及开源项目