我只是好奇

一系列简单区间DP问题

发表于 分类于
本文字数： 7.7k 阅读时长 ≈ 7 分钟

和矩阵连乘类似的套路，举几个问题作为例子。

矩阵连乘问题

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
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
#include <math.h>


/*=======================================
矩阵连乘问题
dp(i, j) = min( dp(i, k) + dp(k + 1, j) + S);
i < k < j;
dp(i, i) = 0;
========================================*/
#define flush(arr, i) memset(arr, i, sizeof(arr))
typedef long long int64;
using namespace std;
const int MAX_ITEM = 128;
//const int oo = 0x7fffffff;
const int oo = 0x3f3f3f3f;


int dp[MAX_ITEM][MAX_ITEM];
int w[MAX_ITEM], pos[MAX_ITEM][MAX_ITEM];


int DP(int l, int r)
{
    if(l == r)
        return 0;

    if(dp[l][r])
        return dp[l][r];


    int ans = oo, tmp = 0;
    for(int i = l; i < r; i++)
    {
        tmp = DP(l, i) + DP(i + 1, r) + w[l - 1] * w[i] * w[r];
        if(ans > tmp)
        {
            ans = tmp;
            pos[l][r] = i;
        }
    }
    return dp[l][r] = ans;
}


void display(int l, int r)
{
    if(l == r)
    {
        printf("A%d", l);
        return;
    }
    printf("(");
    display(l, pos[l][r]);
    display(pos[l][r] + 1, r);
    printf(")");
}


int main()
{
    freopen("0-data.txt", "r", stdin);
    int n;
    while(scanf("%d", &n) != EOF)
    {
        flush(dp, 0);
        flush(pos, 0);
        for(int i = 0; i <= n; i++)
            scanf("%d", w + i);
        printf("%d\n", DP(1, n));
        display(1, n);
    }
    return 0;
}

最优三角剖分

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
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
#include <math.h>
#include <time.h>

/*=======================================
最优三角剖分
dp[i][j] = min(dp[i][x] + dp[x][j] + w(i, x, j));
i <= x <= j
边界条件 dp[i][i + 1] == 0
========================================*/
#define flush(arr, i) memset(arr, i, sizeof(arr))
typedef long long int64;
using namespace std;
const int MAX_ITEM = 110;
const int oo = 0x7fffffff;
//const int oo = 0x3f3f3f3f;

int dp[MAX_ITEM][MAX_ITEM], wei[MAX_ITEM][MAX_ITEM];

int GetWeight(int from, int mid, int to)
{
    return wei[from][mid] + wei[from][to] + wei[mid][to];
}


int DP(int from, int to)
{
    if(to - from == 1)
        return 0;
    if(dp[from][to])
        return dp[from][to];

    int ans = oo;
    for(int i = from + 1; i < to; i++)
        ans = min(ans, DP(from, i) + DP(i, to) + GetWeight(from, i, to));

    return dp[from][to] = ans;
}

int main()
{
    freopen("0-data.txt", "r", stdin);
    int n;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                scanf("%d", &wei[i][j]);
        flush(dp, 0);
        printf("%d\n", DP(0, n - 1));
    }
    return 0;
}

最大m子段和

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
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
#include <math.h>
#include <time.h>

/*=======================================
最大m子段和
9 3
9 8 7 6 5 4 3 2 1
17

dp[k][p]表示前k个元素划分为p个子段最大值的最小值

dp[k][p] = min{dp[k][p], max{dp[x][p - 1] + sum[x + 1][k]}}
p - 1 <= x <= k - 1

========================================*/
#define flush(arr, i) memset(arr, i, sizeof(arr))
typedef long long int64;
using namespace std;
const int MAX_ITEM = 110;
const int oo = 0x7fffffff;
//const int oo = 0x3f3f3f3f;

int dp[MAX_ITEM][MAX_ITEM];
int sum[MAX_ITEM];


int DP(int k, int p)
{
    if(p == 1)
        return dp[k][p] = sum[k];

    if(dp[k][p])
        return dp[k][p];

    int tmp = 0;
    dp[k][p] = oo;

    for(int i = p - 1; i <= k - 1; i++)
    {
        tmp = max(DP(i, p - 1), sum[k] - sum[i]);
        dp[k][p] = min(dp[k][p], tmp);
    }

    return dp[k][p];
}

int main()
{
    int len, p;
    while(scanf("%d%d", &len, &p) != EOF)
    {
        flush(sum, 0);
        flush(dp, 0);
        int tmp;
        for(int i = 1; i <= len; i++)
        {
            scanf("%d", &tmp);
            sum[i] = sum[i - 1] + tmp;
        }
        printf("%d\n", DP(len, p));
    }
    return 0;
}

石子合并问题

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
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
#include <math.h>
#include <time.h>

/*=======================================
石子合并问题
自底向上，求步长为k的时候，步长为k - 1问题的解已知

dp[i][j]表示i -> j的最优解 得分最多/最少
要加上合并的石子总数作为最优值
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]);
========================================*/
#define flush(arr, i) memset(arr, i, sizeof(arr))
typedef long long int64;
using namespace std;
const int MAX_ITEM = 110;
const int oo = 0x7fffffff;
//const int oo = 0x3f3f3f3f;

int dp[MAX_ITEM][MAX_ITEM];
int sum[MAX_ITEM];


int main()
{
    int len;
    while(scanf("%d", &len) != EOF)
    {
        for(int i = 1; i <= len; i++) scanf("%d", sum + i);
        sum[0] = 0;
        for(int i = 1; i <= len; i++)
            sum[i] += sum[i - 1];
        flush(dp, 0);

        for(int sp = 1; sp <= len; sp++)
        {
            for(int i = 1; i + sp <= len; i++)
            {
                int j = i + sp;
                for(int k = i; k < j; k++)
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
                printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
            }
        }
        printf("%d\n", dp[1][len]);
    }
    return 0;
}

最大的算式

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
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
#include <math.h>
#include <time.h>

/*=======================================
最大的算式

dp[k][p] = max(dp[p - 1 ... k - 1][p - 1] * sum[k][p])
表示前i部分插入p个乘号获取的最大值

========================================*/
#define flush(arr, i) memset(arr, i, sizeof(arr))
typedef long long int64;
using namespace std;
const int MAX_ITEM = 110;
const int oo = 0x7fffffff;
//const int oo = 0x3f3f3f3f;

int dp[MAX_ITEM][MAX_ITEM], sum[MAX_ITEM][MAX_ITEM];
int num[MAX_ITEM];

void getSum(int len)
{
    flush(sum, 0);
    flush(dp, 0);
    for(int i = 1; i <= len; i++)
    {
        sum[i][i] = num[i];
        for(int j = i + 1; j <= len; j++)
            sum[i][j] = sum[i][j - 1] + num[j];
    }
/*
    for(int i = 1; i <= len; i++)
        for(int j = i; j <= len; j++)
            j == len ? printf("%d\n", sum[i][j]) : printf("%d ", sum[i][j]);
*/
}

int DP(int k, int p)
{
    if(p == 0)
    {
        dp[k][p] = sum[1][k];
        return dp[k][p];
    }

    if(dp[k][p])
        return dp[k][p];

    int ans = 0;
    for(int i = p - 1; i <= k - 1; i++)
        ans = max(ans, DP(i, p - 1) * sum[i + 1][k]);

    dp[k][p] = ans;
    return ans;
}

int main()
{
    int len, p;
    while(scanf("%d%d", &len, &p) != EOF)
    {
        for(int i = 1; i <= len; i++) scanf("%d", num + i);
        getSum(len);
        printf("%d\n", DP(len, p));
    }
    return 0;
}

最大K乘积问题

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
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
#include <math.h>
#include <time.h>

/*=======================================
最大k乘积问题

dp[k][p] = max(dp[p - 1 ... k - 1][p - 1] * num[k][p])
表示前i项分为j部分的最大乘积

========================================*/
#define flush(arr, i) memset(arr, i, sizeof(arr))
typedef long long int64;
using namespace std;
const int MAX_ITEM = 110;
const int oo = 0x7fffffff;
//const int oo = 0x3f3f3f3f;

int dp[MAX_ITEM][MAX_ITEM], num[MAX_ITEM][MAX_ITEM];
char in[MAX_ITEM];

int getNum(char *in)
{
    int len = strlen(in);
    flush(num, 0), flush(dp, 0);
    for(int i = 1; i <= len; i++)
    {
        int mul = 0;
        for(int j = i; j <= len; j++)
        {
            mul = mul * 10 + in[j - 1] - '0';
            num[i][j] = mul;
        }
    }
/*
    for(int i = 1; i <= len; i++)
        for(int j = i; j <= len; j++)
            j != len ? printf("%d ", num[i][j]) : printf("%d\n", num[i][j]);
*/
}

//前k个分为p部分
int DP(int k, int p)
{
    if(p == 1)
    {
        dp[k][p] = num[1][k];
        return num[1][k];
    }

    if(dp[k][p])
        return dp[k][p];

    int ans = 0;
    for(int i = p - 1; i <= k - 1; i++)
        ans = max(ans, DP(i, p - 1) * num[i + 1][k]);

    dp[k][p] = ans;
    return ans;
}

int main()
{
    int p;
    while(scanf("%s", in) != EOF)
    {
        getNum(in);
        scanf("%d", &p);
        int len = strlen(in);
        printf("%d\n", DP(len, p));
    }
    return 0;
}