Skip to content

Instantly share code, notes, and snippets.

@Abreto
Created October 14, 2013 15:33
Show Gist options
  • Save Abreto/6977579 to your computer and use it in GitHub Desktop.
Save Abreto/6977579 to your computer and use it in GitHub Desktop.
Wikioi 1048 石子归并
/* Wikioi - Problem 1048 */
#include <stdio.h>
#include <limits.h>
int n = 0;
int M[101][101] = {{0}};
int w[101] = {0};
int S[101] = {0};
int dp(int left, int right)
{
int i = 0, k = 0;
int min = 0;
int *ans = &(M[left][right]);
int v0 = 0;
if( left == right )
return 0;
if( *ans )
return (*ans);
min = INT_MAX;
v0 = S[right]-S[left]+w[left];
for(k = left;k < right;++k)
{
int t = dp(left,k) + dp(k+1,right) + v0;
if( min > t )
min = t;
}
return (*ans = min);
}
int
main(void)
{
int i = 0;
scanf("%d", &n);
scanf("%d", w);
S[0] = w[0];
for(i = 1;i < n;++i)
{
scanf("%d", w+i);
S[i] = S[i-1] + w[i];
}
printf("%d\n", dp(0, n-1));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment