这道题算是最简单的区间dp了。。非常久之前写的，搞懂原理了就1A。

传送门：

problem_id=1181">http://acm.zjnu.edu.cn/CLanguage/showproblem?problem_id=1181

状态方程定义：

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);

然后利用三层for就好了。

for(int len=2;len<=n;len++){

		for(int s=1;s<=n-len+1;s++){

			int e=s+len-1;

			f[s][e]=inf;

			for(int k=s;k<=e-1;k++){

				if(f[s][e]>f[s][k]+f[k+1][e]+sum[s][e])

					f[s][e]=f[s][k]+f[k+1][e]+sum[s][e];

			}

		}

	}

最重要的是这个循环，可是事实上也挺简单，首先枚举区间长度，齐次枚举起点s，当然这里每次都要对f[s][e]都初始化为正无穷（视题目情况而定），由于这里每一次的s与e都是不同样的。

然后第三层枚举的是k，k相当于跳板的作用，然后在里面进行dp就好了。

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define maxn 111

#define inf 99999999

int f[maxn][maxn],sum[maxn][maxn],spone[maxn];

int main(){

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&spone[i]);

	for(int i=1;i<=n;i++){

		sum[i][i]=spone[i];

		for(int j=i+1;j<=n;j++){

			sum[i][j]=sum[i][j-1]+spone[j];

		}

	}

	int min1=inf;

	for(int len=2;len<=n;len++){

		for(int s=1;s<=n-len+1;s++){

			int e=s+len-1;

			f[s][e]=inf;

			for(int k=s;k<=e-1;k++){

				if(f[s][e]>f[s][k]+f[k+1][e]+sum[s][e])

					f[s][e]=f[s][k]+f[k+1][e]+sum[s][e];

			}

		}

	}

	if(min1>f[1][n]) min1=f[1][n];

	for(int i=1;i<n;i++){

		swap(spone[i],spone[i+1]);

		for(int l=1;l<=n;l++){

			sum[l][l]=spone[l];

			for(int q=l+1;q<=n;q++){

				sum[l][q]=sum[l][q-1]+spone[q];

			}

		}

		for(int len=2;len<=n;len++){

			for(int s=1;s<=n-len+1;s++){

				int e=s+len-1;

				f[s][e]=inf;

				for(int k=s;k<=e-1;k++){

					if(f[s][e]>f[s][k]+f[k+1][e]+sum[s][e])

						f[s][e]=f[s][k]+f[k+1][e]+sum[s][e];

				}

			}

		}

		if(min1>f[1][n]) min1=f[1][n];

		swap(spone[i],spone[i+1]);

	}

	printf("%d\n",min1);

}

/*

3

2 5 1

*/