http://acm.pku.edu.cn/JudgeOnline/problem?id=1160用opt[i][j]記錄把前i個(gè)郵局建到前j個(gè)村莊中的最優(yōu)解
用cost[i][j]記錄所有在i到j(luò)村莊中，建1個(gè)郵局的最小代價(jià)。顯然郵局應(yīng)該設(shè)到中點(diǎn)。
讓前i個(gè)郵局覆蓋前j個(gè)村莊，第i+1個(gè)郵局覆蓋第j+1至j+k個(gè)村莊(j+k<=n)，則狀態(tài)轉(zhuǎn)移方程為
opt[i+1][j+k]=min{opt[i][j]+cost[j+1][j+k];} (k+j<=n)
#include"stdio.h"
long cost[301][301];
long opt[301][301]; //把前i個(gè)郵局建到前j個(gè)村莊中的最優(yōu)解
int v[301];
void pre(int m,int n)
{
int i,j,mid,k; //記錄所有在i到j(luò)村莊中，建一個(gè)郵局的最小代價(jià)。顯然郵局應(yīng)該設(shè)到中點(diǎn)。
for (i=1;i<=m;i++)
for(j=i;j<=m;j++) //j>=i
{
cost[i][j]=0;
mid=(i+j)/2;
for(k=i;k<=mid;k++)
cost[i][j]+=v[mid]-v[k];
for(k=mid+1;k<=j;k++)
cost[i][j]+=v[k]-v[mid];
}
}
void main()
{
int i,j,k;
int m,n;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++)
scanf("%d",&v[i]);
pre(m,n);
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
opt[i][j]=3000000;
opt[0][0]=0;
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
if(opt[i][j]<3000000)
{
for(k=1;j+k<=m;k++)
if(opt[i+1][j+k]>opt[i][j]+cost[j+1][j+k]) //狀態(tài)轉(zhuǎn)移. 讓前i個(gè)郵局覆蓋前j個(gè)村莊，第i+1個(gè)郵局覆蓋第j+1到第j+k個(gè)村莊。
opt[i+1][j+k]=opt[i][j]+cost[j+1][j+k];
}
printf("%d\n", opt[n][m]);
}