DP经典问题，石子合并
描述：
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。
规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
/* 石子合并问题 由于石子是未成一圈，所以首先我们要把圆圈剪断变成一条直线，而这样的直线有n条（每个石子都可以作为直线的开头） 接下来我们就考虑直线的石子合并问题，这个其实就是矩阵链乘法 dp[i][j]=min{ dp[i][k]+dp[k+1][j]+cost } cost为本次合并带来的代价，cost=ai+ai+1+ai+2……aj */ #include <cstdio> #include <cstring> #define N 110 #define INF 0x3f3f3f3f #define max(a,b) a>b?a:b #define min(a,b) a<b?a:b int dp[N][N][2]; //[0]最小值，[1]最大值 int n,a[N],MAX,MIN; int cost(int i ,int j) { int ans=0; while(i<=j) ans+=a[i++]; return ans; } void solve() { int len,i,j,k,c; for(i=1; i<=n; i++) dp[i][i][0]=dp[i][i][1]=0; //当只有一个石子的时候不存在合并,花费为0 for(len=2; len<=n; len++) for(i=1; i<=n-len+1; i++) { j=i+len-1; dp[i][j][0]=INF; dp[i][j][1]=-INF; c=cost(i,j); for(k=i; k<j; k++) { if(dp[i][k][0]+dp[k+1][j][0]+c < dp[i][j][0]) dp[i][j][0] = dp[i][k][0]+dp[k+1][j][0]+c; if(dp[i][k][1]+dp[k+1][j][1]+c > dp[i][j][1]) dp[i][j][1] = dp[i][k][1]+dp[k+1][j][1]+c; } } MIN=min(MIN,dp[1][n][0]); MAX=max(MAX,dp[1][n][1]); } int main() { while(scanf("%d",&n)!=EOF) { MAX=-INF; MIN=INF; for(int i=1; i<=n; i++) scanf("%d",&a[i]); solve(); //进行一次动态规划 for(int i=2; i<=n; i++) //枚举所有的直线 { int last=a[1]; //将当前直线的头元素放到最后 for(int k=1; k<=n-1; k++) a[k]=a[k+1]; //移动 a[n]=last; //保存好尾元素 solve(); //对当前直线进行一次动态规划 } printf("%d\n%d\n",MIN,MAX); } return 0; }