import java.util.*;
import java.io.*;
public class Main1738n
{
	static int [] sum;
	public static void main(String [] args) throws Exception
	{
		Scanner cin=new Scanner(new FileInputStream("c:\\in.txt"));
		while(true)		
		{
			int n=cin.nextInt();
			if(n==0)break;
			int [] p=new int[n];
			int [][] q=new int[n][n];
			sum=new int[n];
			for(int i=0;i<n;i++)
				p[i]=cin.nextInt();
			sum[0]=p[0];
			for(int i=1;i<n;i++)
				sum[i]=p[i]+sum[i-1];
			int total=f(0,n-1,q,p);
			System.out.println(total);
		}
	}

	public static int f(int i,int j,int [][] q,int [] p)
	{
		if(i==j)
			return 0;
		if(i+1==j)
			return p[i]+p[j];
		if(q[i][j]>0)
			return q[i][j];
		int min=Integer.MAX_VALUE;
		for(int k=i;k<j;k++)
		{
			int tmin=f(i,k,q,p)+f(k+1,j,q,p)+sum[j]-sum[i]+p[i];
			if(min>tmin)
				min=tmin;
		}
		
		return q[i][j]=min;
		
	}
}

• This is a typical DP problem, but you should use leftist tree in this problem to reduce time complexity to O(nlogn) (1003) Petr 2005-10-24 18:37:33
  • DP? it seems not like... (0) xreborner 2005-10-24 20:40:05
    • I mean the original problem is DP, but this problem is modified-greedy. (0) Petr 2005-10-24 20:49:05