poj 1160 DP

原题
题目大意：
有v个村庄，需要建设p个邮局，请你计算出建设邮局的最小费用。
怎么算费用呢 >o<
只要把每个村庄与距离它最近的邮局的距离求和就好了
**
注意哦，邮局一定要建在村庄里哦

题目解析：典型DP
首先我们思考这样一个问题，如果要让你再村庄i到j之间建设一个邮局，怎样建费用最小呢？
当然是建在中间的村庄了~(≧▽≦)/~
于是这个问题就简单了是不是
(^o^)/YES！
于是就有了以下方程
f[i][j]=min(f[k][j-1]+sum[k+1][i],f[i][j])
什么意思呢？
f[i][j]代表前i个村庄建设j个邮局所需要是最小费用
那么其费用就可以由前k个村庄建设j-1个邮局+第k+1个村庄到第i个村庄建设一个邮局的费用转移而来
是不是很有道理
(^o^)/YES!

代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int v,p,zuobiao[300+10],sum[300+10][300+10],f[300+10][30+10];
int main(){
    cin>>v>>p;
    for(int i=1;i<=v;i++)
        cin>>zuobiao[i];
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=v;i++)
        for(int j=1;j<=v;j++)
            for(int k=i;k<=j;k++)
                sum[i][j]+=abs(zuobiao[k]-zuobiao[(i+j)/2]);
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=p;i++)
        f[0][i]=0;//初始化，只有0个村庄当然不用花钱，如果你想花我也不介意
    for(int i=1;i<=v;i++)
        for(int j=1;j<=p;j++)
            for(int k=0;k<i;k++)
                f[i][j]=min(f[k][j-1]+sum[k+1][i],f[i][j]);//请注意，如果是由f[k][j-1]转移而来，k需要从0开始枚举，因为sum[0][i]可能是最小的(也就是建在1到i中间而不是2到i中间)
/*
    for(int i=1;i<=v;i++)
        for(int j=1;j<=p;j++)
            for(int k=1;k<=i;k++)
                f[i][j]=min(f[k-1][j-1]+sum[k][i],f[i][j]);//如果是由f[k][j-1]转移而来，k只需要从1开始枚举就可以啦( ⊙ o ⊙ )！
*/
    cout<<f[v][p]<<endl;
    return 0;
}