dp优化入门

ACM

dp优化入门

线性石子合并问题

问题链接
教程
根据区间dp的经典套路，我们可以列出下面的dp方程
$dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+num[i~j]),k \in [i, j] $

轻松的写出下面的程序：
时间复杂度为$ (O(n^3) $
但是时间复杂度不对qaq

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
#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 = 1000+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
ll read()
{
    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;
int num[maxn];
int dp[maxn][maxn];
int pre[maxn];
void solve(){
    cls(dp, 0x3f);
    inc(i, 1, n) dp[i][i] = 0;
    inc(l, 2, n){
        inc(i, 1, n+1-l){
            inc(k, i, l+i-1){
                dp[i][l+i-1] = min(dp[i][l+i-1], dp[i][k]+dp[k+1][l+i-1]+pre[l+i-1]-pre[i-1]);
            }
        }
    }
}
int main()
{
    n=read();
    cls(pre, 0);
    inc(i, 1, n)  num[i] = read(), pre[i] = pre[i-1]+num[i];
    solve();
    printf("%d\n", dp[1][n]);
    return 0;
}

下面想想怎么优化
四边形不等式优化：

　1、区间包含的单调性：如果对于 i≤i’ ＜j≤j’，有 w(i’,j)≤w(i,j’)，那么说明w具有区间包含的单调性。（可以形象理解为如果小区间包含于大区间中，那么小区间的w值不超过大区间的w值）
2、四边形不等式：如果对于 i≤i’＜j≤j’，有 w(i,j)+w(i’,j’)≤w(i’,j)+w(i,j’)，我们称函数w满足四边形不等式。（可以形象理解为两个交错区间的w的和不超过小区间与大区间的w的和）

下面给出两个定理：
1、如果上述的 w 函数同时满足区间包含单调性和四边形不等式性质，那么函数 m 也满足四边形不等式性质
我们再定义 s(i,j) 表示 m(i,j) 取得最优值时对应的下标（即 i≤k≤j 时，k 处的 w 值最大，则 s(i,j)=k）。此时有如下定理
2、假如 m(i,j) 满足四边形不等式，那么 s(i,j) 单调，即 s(i,j)≤s(i,j+1)≤s(i+1,j+1)。

因此第三维只要枚举常数的决策点就行了，相当于时间复杂度是常数项

新的算法

时间复杂度为$O(nlogn) $
link

取石子-环形

破环为链，然后在后面曾一倍使之变成线性的结构进行dp

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
#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 = 1000+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
ll read()
{
    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;
int num[maxn];
int dp[maxn][maxn];
int pre[maxn];
void solve(){
    cls(dp, 0x3f);
    inc(i, 1, 2*n) dp[i][i] = 0;
    dec(i, 2*n, 1){
        inc(j, i+1, min(2*n, n+i-1)){
            inc(k, i, j-1){
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]);
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for(int i=1; i<=n; i++){
        ans = min(ans, dp[i][i+n-1]);
    }
    printf("%d ", ans);
    cls(dp, -1);
    inc(i, 1, 2*n) dp[i][i] = 0;
    dec(i, 2*n, 1){
        inc(j, i+1, min(2*n, n+i-1)){
            inc(k, i, j-1){
                dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]);
            }
        }
    }
    ans = -1;
    for(int i=1; i<=n; i++){
        ans = max(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
}
int main()
{
    while(~scanf("%d", &n)){
        cls(pre, 0);
        inc(i, 1, n)  num[i] = read(), pre[i] = pre[i-1]+num[i];
        inc(i, n+1, 2*n) num[i] = num[i-n], pre[i] = pre[i-1]+num[i];
        solve();
    }
    return 0;
}

生命仪式

dp[i][j]表示区间[i, j]的最优的值，最后剩下的是i,j+1石子

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
#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 = 8e2+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
ll read()
{
    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;
int num[maxn];
int dp[maxn][maxn];
void solve(){
    cls(dp, 0);
    //dp[i][j]表示最后剩下i,j+1石子的最优的答案
    dec(i, 2*n-2, 1){
        inc(j, i+1, min(2*n-1, i+n-1)){
            inc(k, i, j-1){
                //保存的是k+1石子
                dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]+num[i]*num[k+1]*num[j+1]);
                //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            }
        }
    }
    int ans = -1;
    inc(i, 1, n){
        ans = max(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
}
int main()
{
    while(~scanf("%d", &n)){
        inc(i, 1, n) scanf("%d", &num[i]);
        inc(i, n+1, 2*n) num[i] = num[i-n];
        solve();
    }
    return 0;
}
/*
4
1 2 3 4
*/

k进制Huffman编码

要加入若干个虚拟的节点，使得整棵树变得完整
k进制的huffman树

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
#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 = 100000+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
ll read()
{
    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, k;
struct Node{
    ll w;
    int dep;
    bool operator < (const Node &b) const {
        if(w!=b.w) return w>b.w;
        else return dep>b.dep;
    }
}node[maxn];
priority_queue<Node> pq;
void solve(){
    ll ans = 0;
    int maxl = -1;
    while(n>1){
        int maxd=0; ll tot = 0;
        inc(i, 1, k){
            tot += pq.top().w;
            maxd = max(maxd, pq.top().dep);
            pq.pop();
        }
        pq.push(Node{tot, maxd+1});
        ans += tot;
        maxl = max(maxl, maxd);
        n -= (k-1);
    }
    printf("%lld\n%d\n", ans, maxl);
}
int main()
{
    n=read(), k=read();
    ll w;
    inc(i, 1, n){
        w=read();
        pq.push(Node{w, 1});
    }
    int res = (n-1)%(k-1);
    if(res){
        res = k-1-res;
        n += res;
    }
    inc(i, 1, res)pq.push(Node{0, 1});
    solve();
    return 0;
}

未解决的问题

本文标题:dp优化入门

文章作者:Babydragon

发布时间:2018-08-27, 17:06:58

最后更新:2018-08-27, 21:16:23

原始链接:http://baolintian.github.io/2018/08/27/dp优化入门/

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

文章目录
  1. 1. 线性石子合并问题
    1. 1.1. 新的算法
  2. 2. 取石子-环形
    1. 2.1. ac code
  3. 3. 生命仪式
    1. 3.1. ac code
  4. 4. k进制Huffman编码
    1. 4.1. ac code
  5. 5. 未解决的问题
{{ live2d() }}