HDU 2829 Lawrence【四边形优化】

http://acm.hdu.edu.cn/showproblem.php?pid=2829

HDU 2829 Lawrence

大意：
  有一条直线型的铁路，上面有n个火车站，每个火车站有各自的权重a[i],
  现有m枚炮弹，每枚炮弹可炸毁一段铁路。
  已知整条铁路的权重W = sum(a[i]*a[j]),其中火车站编号i<j且i与j相连
  问如何使用这m枚炮弹使W最小，输出最小的W值

分析：
sum[i]表示从1到i的权重和,包含i
cost[i][j]表示不炸毁[i,j]间的站点所需的花费，包含站点i和j
dp[i][k]表示从1到i炸毁k条路后所需的最少花费
则有：dp[i][k]=min(dp[j][k-1]+sum[j+1][i])(j=k,...,i-1)
用四边形不等式优化

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int N = 1000+5;
int sum[N];
int num[N];
int cost[N][N];
int s[N][N];
int dp[N][N];
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)break;
        int i,j,k;
        memset(cost,0,sizeof(cost));
        sum[0] = 0;
        num[0] = 0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            sum[i]=sum[i-1]+num[i];
        }
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)
            {
                cost[i][j]=cost[i][j-1]+(sum[j-1]-sum[i-1])*num[j];
            } 

    
        for(i=0;i<=n;i++)
        {
            s[i][0]=0;
            dp[i][0]=cost[1][i];
        }
        for(k=1;k<=m;k++)
        {
            s[n+1][k]=n-1;
          for(i=n;i>k;i--)
          {
              dp[i][k]=dp[k][k-1]+cost[k+1][i];
              s[i][k]=k;
              for(j=s[i][k-1];j<=s[i+1][k];j++)
              {
                  int temp = dp[j][k-1]+cost[j+1][i];
                  if(temp<dp[i][k])
                  {
                      dp[i][k]=temp;
                      s[i][k]=j;
                  }
              }
          }
        }
    
        //cout<<dp[n][m]<<endl;
        printf("%d\n",dp[n][m]);
    }
    return 0;
}