有n堆石子，第i堆石子重量(a_i),每次操作将两堆相邻石子合并，合并后的石子重量以及耗费的体力均为两堆石子重量之和，询问最少的体力耗费，(nleq 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 <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
int s[301],dp[301][301];
template<class free>
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<class free>
il free Min(free a,free b){
return a<b?a:b;
}
dfs实现
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define intmax 0x7fffffff
using namespace std;
int a[301],dp[301][301];
il int dfs(int,int);
template<class free>
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<class free>
il free Min(free a,free b){
return a<b?a:b;
}
il int dfs(int l,int r){
if(l==r)return 0;
if(dp[l][r])return dp[l][r];dp[l][r]=intmax;
for(int k(l);k<r;++k)
dp[l][r]=Min(dp[l][r],dfs(l,k)+dfs(k+1,r));
dp[l][r]+=a[r]-a[l-1];return dp[l][r];
}