分段DP

分段DP

Axell 8月 22, 2018

分段DP,即将数据进行分段操作,而取得最优解的DP

通常的定义为: f[i][j]表示将前i个数据分为j组时,所能得到的最优解

例题

快餐店

题目描述

排成一条直线的公路上有N个加油站，为了方便加油站的员工吃饭，需要在这N个加油站点位置选K个开设快餐店。那么问题来了，怎样选取能使得每个加油站都可以就近吃饭。所谓的就近吃饭，就是每个加油站的人员会去最近的快餐店吃饭，需要走两个加油站之间的距离。我们的目标是让每个加油站到最近快餐店的距离之和最小（具体可以看样例解释）。

输入

输入N, K

然后接下来N行，每行输入一个整数ai，表示加油站的位置（这个位置的值是递增的）

输出

输出最小的距离之和，格式见样例输出

样例输入

样例输出

Total distance sum = 8

提示

【样例说明】

选择第2，4，6站点作为快餐店，那么前三个站点人会去第一个快餐店，4和5站点人回去第二个快餐店，剩下的第三个快餐店。距离之和为：

(1+0+6)+(0+1)+0=8

【数据规模和约定】

1<=N<=200 1<=K<=30 K<=N 1<=ai<=100000

思路

本质上是让我们求出 1~n 分成 m 段的最优解

定义f[i][j]表示: 第1~~i个快餐店中分出j组时,总路程的最小值; 定义cost[i][j]表示i~~j之间总路程的最小值

状态转移方程为: f[k][i]=min(f[k][i],f[j][i-1]+cost[j+1][k])
这么定义的原因:

i枚举已有的组数
k枚举1~k的最小值
j枚举新的一段的起点
即: 在 1~~j 已经分成 i-1 段时,增加一段 j+1~~k 使得其分成 i 段 (其实就是在找一个合适的 j 使得 1~k 最优)
很显然,这种方式无后效性,可用DP求最优解

代码

#include <bits/stdc++.h>
using namespace std;

int n,m,a[205],cost[205][205],f[205][205],tmp;

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for (int i=1;i<=n-1;++i){
        for (int j=i+1;j<=n;++j){
            tmp=a[(i+j)/2];
            for (int k=i;k<=j;++k){
                cost[i][j]+=abs(a[k]-tmp);
            }
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j)
            f[i][j]=1e9;
        f[i][1]=cost[1][i];
    }
    for (int i=2;i<=m;++i){
        for (int j=i;j<=n;++j){
            for (int k=j+1;k<=n;++k){ //其实内外两层循环可以换一下,只是这样方便一些
                f[k][i]=min(f[k][i],cost[j+1][k]+f[j][i-1]);
            }
        }
    }
    cout<<"Total distance sum = "<<f[n][m]<<endl;  //输出将1~n分为m段时的最优解
    return 0;
}

乘号加号

题目描述

题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如： N=5, K=2，5个数字分别为1、2、3、4、5，可以加成： 1*2*(3+4+5)=24 1*(2+3)*(4+5)=45 (1*2+3)*(4+5)=45 ……

输入

输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中(2< =N< =15, 0< =K< =N-1)。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。

输出

输出文件仅一行包含一个整数，表示要求的最大的结果最后的结果< =maxlongint

样例输入

5 2
1 2 3 4 5

样例输出

提示

对于30%的数据，N< = 10；对于全部的数据，N < = 100。

思路

就是用乘号将数字的和分离开来,求出分成k+1段的最优解

cost[i]是前缀和数组

代码

#include <bits/stdc++.h>
using namespace std;

int n,m,a[105];
long long f[105][105];

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        a[i]+=a[i-1];
    }
    for (int i=1;i<=n;++i){
        f[i][1]=a[i];
    }
    for (int i=2;i<=m+1;++i){  //注意这里要+1
        for (int j=1;j<=n;++j){
            for (int k=j+1;k<=n;++k){  //内外同样可以换一下
                f[k][i]=max(f[k][i],f[j][i-1]*(a[k]-a[j])); 
            }
        }
    }
    cout<<f[n][m+1];
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/17/