poj1738 an old stone game
石子合并，经典dp，我们定义dp[i][j]表示从i开始的j个石子合并的最小（最大）代价，dp方程为：
dp[i][j]=min{dp[i][k]+dp[i+k][j-k]+sum[i][j]},sum[i][j]表示从i开始的j个数的和。
这个题目由于规模太大了，无法开一个5000*5000的数组，需要用到其他方法，discuss里面说用Garsia Wachs算法，没听说过，有待研究。
下面的是我处理小规模的dp代码：
#include
#include
using namespace std;
const int INF=1000000001;
const int N = 500;
int m[N],p[N][N],dp[N][N];
inline int MIN(int a,int b)
{
return (a>b)?b:a;
}
int main()
{
int i,j,n,k,ty;
while(1)
{
scanf("%d",&n);
if(!n)
break;
memset(dp,0,sizeof(dp));
memset(m,0,sizeof(dp));
for(i=0;i=0;i--)
{
for(j=1;j<=n-i;j++)
{
p[i][j]=p[i][j-1]+m[i+j-1];
}
}
for(j=2;j<=n;j++)
{
ty=n-j;
for(i=0;i<=ty;i++)
{
k=1;
dp[i][j]=dp[i][k]+p[i][k]+dp[i+k][j-k]+p[i+k][j-k];
for(k=2;k