1784.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"memory.h"

int p[202];
int q[202];
int s[202][202];
int ans[202][202];
int sum[202];


int main()
{
	int n , i, j, l, k, temp, r;
	
	while(1)
	{
		scanf( "%d", &n );
		if( n == 0 ) break;

		for( i=1; i<=n; i++ )
		{
			scanf( "%d", &p[i] );
			sum[i] = p[i];
		}

		sum[0] = 0;
		sum[n+1] = 0;
		p[n+1] = 0;

		for( i=0; i<=n; i++ )
		{
			scanf( "%d", &q[i] );
			sum[i+1] += sum[i] + q[i];
		}
	
		for( i=1; i<=n; i++ )
		{
			ans[i][i] = p[i] + q[i-1] + q[i];
			ans[i][i-1] = 0;
			s[i][i] = i;
		}
		ans[n+1][n] = 0;

		for( l=1; l<n; l++ )
		for( i=1; i+l<=n; i++ )
		{
			j = i+l;
	
			ans[i][j] = 999999999;
				
			for( k = s[i][j-1]; k<=s[i+1][j]; k++ )
			{
				if( ( temp = ans[i][k-1] + ans[k+1][j] ) < ans[i][j] )
				{
					ans[i][j] = temp;
					s[i][j] = k;
				}
			}

			ans[i][j] += sum[j+1] - p[j+1] - sum[i-1];
		}
		printf( "%d\n", ans[1][n] );
	}
	return 0;
}