dp优化总结

ACM

dp优化

学习的博客

决策单调性优化dp

决策单调性例题

原题
题解

题解

可以很容易的列出:
dp[i][j] 表示的是前j个人分成i组的最小花费

$ dp[i][j] = min(dp[i-1][k], cost(k+1, j)), k \lt j $

然后用决策单调性优化dp
这题可以分治nlogn

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 4000+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, k;
int unhappy[maxn][maxn];
int cost[maxn][maxn];
int pre_sum[maxn];
int dp[maxn][maxn];
void pre(){
    inc(i, 1, n){
        cls(pre_sum, 0);
        inc(j, 1, n){
            cost[i][j] = cost[i-1][j]+pre_sum[j-1]+unhappy[i][j];
            pre_sum[j] = pre_sum[j-1]+unhappy[i][j];
        }
    }
}
int cal(int i, int j){
    return cost[j][j]+cost[i-1][i-1]-cost[i-1][j]-cost[j][i-1];
}
int decision[maxn][maxn];
void solve(){
    cls(dp, 0x3f);
    inc(i, 1, n) dp[1][i] = cal(1, i), decision[1][i] = 1;
    inc(i, 2, k){
        decision[i][n+1] = n;
        for(int j=n; j>0; j--){
            for(int l=decision[i-1][j]; l<=decision[i][j+1]; l++){
                if(dp[i-1][l]+cal(l+1, j)<dp[i][j]){
                    dp[i][j] = dp[i-1][l] + cal(l+1, j);
                    decision[i][j] = l;
                }
            }
        }
    }
    printf("%d\n", dp[k][n]>>1);
}
int main()
{
    n=readint(), k=readint();
    inc(i ,1, n) inc(j, 1, n) unhappy[i][j] = readint();
    pre();
//    inc(i, 1, n){
//        inc(j, i+1, n){
//            cout<<i<<" "<<j<<" "<<cal(i, j)<<endl;
//        }
//    }
    solve();
    return 0;
}

斜率优化

题目

原题

题解

题意：
给出N个树，从左到右编号为1~N，我们有一个电锯，电锯有电的时候可以使得一棵树的高度减少1，我们充电的花费是已经砍倒的最大编号（i）的那棵树的B【i】的值，我们的电锯一开始是充满电的，问将所有树都砍倒的最小花费。

贪心后，可以列出下面的dp方程：

$dp[i] = min(dp[j]+b[j]·a[i]), j<i$

什么意思呢？
就是我要砍第i棵树的时候，第j棵是我砍到的最高的树，代价就是b[j]*a[i]
斜率优化的经典套路，设j>k, 满足什么条件j不会被忽视呢？

$dp[j]+b[j]·a[i]<dp[k]+b[k]·a[i], so \frac{dp[j]-dp[k]}{b[k]-b[j]} \lt a[i]$

一般分子分母交叉相乘，但是这一道题要用除法，防止爆long long

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
ll a[maxn], b[maxn];
ll sum[maxn];
ll dp[maxn];
int que[maxn];
ll up(int i, int j){
    return dp[i]-dp[j];
}
ll down(int i, int j){
    return b[j]-b[i];
}
ll cal_dp(int i, int j){
    return dp[j]+a[i]*b[j];
}
int main()
{
    n=readint();
    inc(i, 1, n) a[i]=readll();
    inc(i, 1, n) b[i]=readll();
    //inc(i, 1, n) sum[i] = sum[i-1]+a[i];
    int head=0, tail=0;
    que[tail++] = 1;
    inc(i ,2, n){
        while(head+1<tail&&1.0*up(que[head+1], que[head])/down(que[head+1], que[head])<=a[i]*1.0) head++;
        dp[i] = cal_dp(i, que[head]);
        while(head+1<tail&&1.0*up(i, que[tail-1])/down(i, que[tail-1])<=1.0*up(que[tail-1], que[tail-2])/down(que[tail-1], que[tail-2])) tail--;
        que[tail++] = i;
    }
    printf("%lld\n", dp[n]);
    return 0;
}

未解决的问题

本文标题:dp优化总结

文章作者:Babydragon

发布时间:2018-08-29, 22:16:16

最后更新:2018-08-30, 00:39:07

原始链接:http://baolintian.github.io/2018/08/29/dp优化总结/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 决策单调性优化dp
  2. 2. 决策单调性例题
    1. 2.1. 题解
    2. 2.2. ac code
  3. 3. 斜率优化
    1. 3.1. 题目
    2. 3.2. 题解
    3. 3.3. ac code
  4. 4. 未解决的问题
{{ live2d() }}