合并石子

题目描述

在一个直线上有$n$个石子堆，第$i$堆有$a_i$个石子。现在要把这些石子变成一堆，只能合并相邻的两堆。耗费体力为新的一堆的石子数。

输入格式

共两行。

第一行一个整数，表示$n$。

第二行$n$个整数，以空格间隔。表示$a_i$。

数据范围与约定

$n<100,a_i<10^6$

代码

#include<bits/stdc++.h>
using namespace std;
#define float double
#define mian main
#define ture true
int fr[101],dp[101][101],s[101];
int read()
{
    int x=0,f=1;
	char ch=getchar();
    while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
    while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
    return x*f;
}
void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
signed main()
{
    int n,p=0;
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<n;i++)
    {
    	cin>>fr[i];
    	p+=fr[i];
    	s[i]=p;
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<n;j++)
		{
			int q=i+j-1;
			if(q>n)break;
			for(int k=j;k<q;k++)dp[j][q]=min(dp[j][q],dp[j][k]+dp[k+1][q]+s[q]-s[j-1]);
		}
	}
	write(dp[0][n-1]);
	return 0;
}

求各位dalao来找错！