AOJ 2415

DPの練習によさそうなやつ

#include<stdio.h>
#include<algorithm>
using namespace std;
long long dp1[5000][5000];
int dp2[5000][5000];
long long b[5000];
long long c[5000];
int main(){
	int a;
	scanf("%d",&a);
	//while(~scanf("%d",&a)){
		for(int i=0;i<a;i++){
			scanf("%lld",b+i);
		}
		for(int i=0;i<=a;i++){
			for(int j=0;j<=a;j++){
				dp1[i][j]=999999999999999LL;
				dp2[i][j]=0;
			}
			dp1[i][i]=0LL;
			dp2[i][i]=i;
		}
		for(int i=0;i<=a;i++)c[i]=0LL;
		for(int i=0;i<a;i++)c[i+1]=c[i]+b[i];
		for(int w=1;w<=a;w++){
			for(int i=0;i+w<a;i++){
				int j=i+w;
				for(int k=dp2[i][j-1];k<=dp2[i+1][j];k++){
					long long val=dp1[i][k]+dp1[k+1][j]+(c[j+1]-c[i]);
					if(val<dp1[i][j]){
						dp1[i][j]=val;
						dp2[i][j]=k;
					}
				}
			}
		}
	//	for(int i=0;i<=a;i++){
	//		for(int j=0;j<=a;j++)
	//			printf("%15lld ",dp1[i][j]);
	//		printf("\n");
	//	}
		printf("%lld\n",dp1[0][a-1]);
	
}