[codevs3002]石子归并3

题目（codevs）
就是这个定理：若dp满足四边形不等式，则s(决策点)满足：s(i,j-1)<=s(i,j)<=s(i+1,j)

#include <bits/stdc++.h>
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;int ck=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=-1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	e*=ck;
}
const int N=3050;
int n;
int w[N],sum[N];
int dp[N][N],s[N][N];
int main(){
	read(n);
	for (int i=1;i<=n;++i) read(w[i]);
	for (int i=1;i<=n;++i) sum[i]=sum[i-1]+w[i];
	for (int i=1;i<=n;++i) s[i][i]=i;
	for (int l=2;l<=n;++l){
		for (int i=1;i+l-1<=n;++i){
			int j=i+l-1;dp[i][j]=0x3f3f3f3f;
			for (int k=s[i][j-1];k<=s[i+1][j];++k){
				int tmp=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
				if (tmp<dp[i][j])dp[i][j]=tmp,s[i][j]=k;
			}
		}
	}
	printf(
	return 0;
}