区间型动态规划


这里是关于区间型动态规划的题目以及程序

区间型动态规划

石子归并

题目描述 Description

有$n$堆石子排成一列，每堆石子有一个重量$w[i]$, 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和$w[i]+w[i+1]$。问安排怎样的合并顺序，能够使得总合并代价达到最小。

要求$n$个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述 Input Description

第一行一个整数$n（n \leq 100）$
第二行$n$个整数$w_1,w_2…w_n (w_i \leq 100)$

输出描述 Output Description

一个整数表示最小合并代价

样例输入 Sample Input

4
4 1 1 4

样例输出 Sample Output

18

数据范围及提示 Data Size & Hint

无

Consideration 想法

状态方程:$ dp [ i ] [ j ] $表示把区间$[i,j]$合并所需要的最小花费.

状态转移方程:$dp[i][j]=dp[i][k]+dp[k+1][j]+(w[i]+w[i+1]+…+w[j-1]+w[j])$.

可见先要求出小区间,才能求大区间.

有两种做法:

1.先求出所有长度为$2$的区间,再求出所有长度为$3$的区间…最后求出长度为$n$的区间.

2.先求出区间右端点是$2$的区间,再求出区间右端点时$3$的区间…最后求出区间右端点是$n$的区间.

注意:

1.解法1中的小区间都是求过的,可以直接使用.但是注意初始值$dp[i][j]=INF$.画个图可以看出来$k$的取值范围是$[i,j)$.

2.解法2中在求解以$j$为区间右端点的区间时,区间右端点小于$j$的区间都可以直接使用.如果求区间$[i,j]$,那么要用到区间$[i,k]$和$[k+1,j]$,其中$[i,k]$可以直接使用,而要使用$[k+1,j]$就必须在求解$[i,j]$之前先求解$[k+1,j]$,又因为$k+1>i$,所以在求解区间右端点为$j$的区间时,左端点要从右向左枚举.

The Code Of My Program AC代码

解法 1

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
102
103
104
105
106
/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
const int maxn=100+5;
int n;
int dp[maxn][maxn],s[maxn];


inline ll read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch \leq '9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}

void print(){
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			printf("%2d ",dp[i][j]);
		}
		printf("\n");
	}
}

void init(){
    n=read();
    for(int i=1;i \leq n;i++){
        int t=read();
        s[i]=s[i-1]+t;
    }
}

void solve(){
    for(int r=2;r \leq n;r++)//区间长度 
        for(int l=1;l \leq n-r+1;l++){//区间左端点 
            int j=l+r-1; dp[l][j]=INF;//区间右端点 
            for(int k=l;k<j;k++) {
				dp[l][j]=min(dp[l][j],dp[l][k]+dp[k+1][j]+s[j]-s[l-1]);
			} 
        }
    printf("%d\n",dp[1][n]);
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    init();
    solve();
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}

解法 2

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
/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
const int maxn=100+5;
int n;
int dp[maxn][maxn],s[maxn];

inline ll read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch \leq '9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}

void init(){
    scanf("%d",&n);
    for(int i=1;i \leq n;i++){
        int t; scanf("%d",&t);
        s[i]=s[i-1]+t;
    }
}

void solve(){
    for(int j=1;j \leq n;j++)
        for(int i=j-1;i;i--){
            dp[i][j]=INF;
            for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
        }
    printf("%d\n",dp[1][n]);
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    init();
    solve();
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}

能量项链

题目描述 Description

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有$N$颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为$m$，尾标记为$r$，后一颗能量珠的头标记为$r$，尾标记为$n$，则聚合后释放的能量为$ m * r * n $ （Mars单位），新产生的珠子的头标记为$m$，尾标记为$n$。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设$N=4$，$4$颗珠子的头标记与尾标记依次为$(2,3) (3,5) (5,10) (10,2)$。我们用记号$⊕$表示两颗珠子的聚合操作，$(j⊕k)$表示第$j,k$两颗珠子聚合后所释放的能量。则第$4、1$两颗珠子聚合后释放的能量为：

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为

输入描述 Input Description

第一行是一个正整数$N（4 \leq N \leq 100）$，表示项链上珠子的个数。第二行是$N$个用空格隔开的正整数，所有的数均不超过$1000$。第$i$个数为第$i$颗珠子的头标记$（1 \leq i \leq N）$，当$ i < N $时，第$i$颗珠子的尾标记应该等于第$i+1$颗珠子的头标记。第$N$颗珠子的尾标记应该等于第$1$颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出描述 Output Description

只有一行，是一个正整数$E（E \leq 2.1 * 10^9）$，为一个最优聚合顺序所释放的总能量。

样例输入 Sample Input

4
2 3 5 10

样例输出 Sample Output

710

数据范围及提示 Data Size & Hint

无

Consideration 想法

$d[i][j]$表示合并区间$[i,j]$得到的最大能量。

$ d [ i ] [ j ] = max(d [ i ] [ k ] + d [ k+1 ] [ j ] + a[i] * a[k+1] * a[j+1]) $

其中$a[i]$表示第$i$颗珠子的头标记(注意搞清楚这几个头尾的关系,差点被搞晕)

假设以$1$号珠子为起点，则最大能量为$d[1][n]$。

现在没说起点是哪个，最直接想到的方法是枚举。可是，跑一次的复杂度是$O(n^3)$，算上枚举的话就是$O(n^4)$，对于$n=100$，很有可能会$TLE$，得有个改进的方法。（天梯上面的数据没卡时间，我枚举法交上去居然A了）

假设有五颗珠子，编号分别是$1 \; 2 \; 3 \; 4 \; 5$，则以$2$为起点时的顺序是$2 \; 3 \; 4 \; 5 \; 1$。

两次计算中重复计算的量有$[2,3],[3,4],[4,5],[2,4],[3,5],[2,5]$(方括号中的数字代表编号)

我们可以考虑将数组扩大一倍,令$a[n+1]=a[1],a[n+2]=a[2]…a[n+n]=a[n]$.(最后一个没用,因为是循环)

这样一i为起点的答案就是$d[i][i+n-1]$，扫一遍取最大就行了。

这样就将复杂度降为$O(n^3)$了。

The Code Of My Program AC代码

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
/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;

inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch \leq '9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    int a[210];
int d[210][210];
int n;

    int mv = 0;
    n=read();
    for(int i = 1; i  \leq  n; ++i){
        a[i]=read();
        a[i+n] = a[i];
    }
    
    for(int i = n+n-1; i >= 1; --i)
    {
        for(int j = i+1; j < min(n+n,i+n); ++j)
        {
            d[i][j] = max(d[i][j-1]+a[i]*a[j]*a[j+1], d[i+1][j]+a[i]*a[i+1]*a[j+1]);
            for(int k = i+1; k < j-1; ++k){
                d[i][j] = max(d[i][j], d[i][k]+d[k+1][j]+a[i]*a[k+1]*a[j+1]);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i  \leq  n; ++i)ans = max(ans,d[i][i+n-1]);
    cout<<ans<<endl;
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}

矩阵取数游戏

题目描述 Description

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的$ n * m $ 的矩阵，矩阵中的每个元素$a_{ij}$均为非负整数。游戏规则如下：

  1. 每次取数时须从每行各取走一个元素，共$n$个。$m$次后取完矩阵所有元素；
  2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
  3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分= 被取走的元素值$ * 2^i$，其中$i$表示第$i$次取数（从$1$开始编号）；
  4. 游戏结束总得分为$m$次取数得分之和。
    帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入描述 Input Description

第$1$行为两个用空格隔开的整数$n$和$m$。
第$ 2 $ ~ $ n+1 $ 行为$ n * m $矩阵，其中每行有m个用单个空格隔开的非负整数。

输出描述 Output Description

输出 仅包含 1 行，为一个整数，即输入矩阵取数后的最大得分。

样例输入 Sample Input

2 3
1 2 3
3 4 2

样例输出 Sample Output

82

数据范围及提示 Data Size & Hint

样例解释

第 1 次：第$1$行取行首元素，第$2$行取行尾元素，本次得分为$1 * 2^1+2 * 2^1=6$
第 2 次：两行均取行首元素，本次得分为$2 * 2^2 + 3 * 2^2 = 20$
第 3 次：得分为$3 * 2^3+4 * 2^3=56$。总得分为$6+20+56=82$

【限制】
$ 60 % $ 的数据满足：$1 \leq n, m \leq 30$, 答案不超过$10^{16}$
$100 % $ 的数据满足：$1 \leq n, m \leq 80, 0 \leq aij \leq 1000$

Consideration 想法

首先读题后，我们发现行与行之间相互独立没有干扰，这样我们就可以读一行处理一行，每一行都是一个单独的问题，相当于给了n组数据，求出答案的和。
这样我们把空间从n²降到了n。

接下来开始考虑思路。不难发现，取走一部分数字后，剩下的数字总是形成一个区间。由于取走的数的个数已知，剩下的数字按顺序的权值也就知道了，由此得出，这是一个区间DP，和石子合并类似。它满足最优子结构，也满足无后效性。

用f[i][j]表示区间[i, j]的最优解，有两种解法

f[i][j] = max(a[i] + 2 * f[i+1][j], a[j] + 2 * f[i][j-1]);//直接计算数的权值
f[i][j] = max(a[i]*2^(m-j+i) + f[i+1][j], a[j]*2^(m-j+i) + f[i][j-1])//每次翻倍

第一种，就是先做一个二的幂次方表，直接计算，很好理解。
第二种，也是更加方便的一种，只需要每次将小区间乘二即可，应用了乘法分配律的原理。进行完整个区间后，区间长度小乘的次数就多，最后的效果也是二的幂次方。应该也不难理解吧

这里最恶心的是要高精度…..所以我wa了

The Code Of My Program WA代码

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
//codevs1166 矩阵取数游戏 区间DP+高精 
//copyright by ametake
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int maxn=80+5;
const int maxl=32;
int n,m;
int a[maxn],f[maxn][maxn],aa[maxn],bb[maxn],ans[maxn];
 
 
int main()
{
    int ans=0;
    scanf("%d%d",&n,&m);//n行m列 
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++) scanf("%d",&a[j]);
        for (int j=1;j<=m;j++) f[j][j]=a[j];
        for (int j=1;j<=m-1;j++)//区间长度 
        {
            for (int k=1;k<=m-j;k++)//起点
            {
                int l=k+j;
                f[k][l] = max(a[k]  + 2 * f[k+1][l], a[l] + 2 * f[k][l-1]);
            } 
        }
        ans+=2*f[1][m];
    }
    printf("%d\n",ans);
    return 0;
}

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

ChenShou <br><br> 已经读大三 , 懒散无志向 <br> 专业是电子 , 却喜欢算法 <br><br> 不怎么会使用电焊 <br> 但是爱折腾服务器 <br><br> 心随地迁，自由彼方<br> 尽管陌路，仍可相识