有n堆石子，第i堆石子重量\(a_i\),每次操作将两堆相邻石子合并，合并后的石子重量以及耗费的体力均为两堆石子重量之和，询问最少的体力耗费，\(n\leq 300\)。
解
注意到相邻两堆石子合并，其实就能想到区间递推了，于是设\(f[l][r]\)表示合并第l堆石子到第r堆石子的最小耗费的体力值，设s为a的前缀和，于是我们有
\[f[l][r]=\min_{k=l}^{r-1}(f[l][k]+f[k+1][r]+s[r]-s[l-1])\]
边界：\(f[i][i]=0,i=1,2,3...,n\)，其余无限大
答案：\(f[1][n]\)
参考代码：
阶段实现
#include#include #include #define il inline#define ri registerusing namespace std;int s[301],dp[301][301];template il free Min(free,free);int main(){ int n; memset(dp,66,sizeof(dp)),scanf("%d",&n); for(ri int i(1);i<=n;++i) scanf("%d",&s[i]),s[i]+=s[i-1],dp[i][i]=0; for(ri int i,j(1),k;j<=n;++j) for(i=j-1;i;dp[i][j]+=s[j]-s[i-1],--i) for(k=j;k>i;--k) dp[i][j]=Min(dp[i][j],dp[i][k-1]+dp[k][j]); printf("%d",dp[1][n]); return 0;}template il free Min(free a,free b){ return a
dfs实现
#include#include #define il inline#define ri register#define intmax 0x7fffffffusing namespace std;int a[301],dp[301][301];il int dfs(int,int);template il free Min(free,free);int main(){ int n,i;scanf("%d",&n); for(i=1;i<=n;++i) scanf("%d",&a[i]),a[i]+=a[i-1]; printf("%d",dfs(1,n)); return 0;}template il free Min(free a,free b){ return a