• 【备战NOIP】专题复习2-动态规划-区间DP

  ---

  【备战NOIP】专题复习2-动态规划-区间DP

  区间DP模板

  题目链接：石子合并（弱化版）

  题意：设有 $N(N\le 300)$ 堆石子排成一排，其编号为 $1,2,3,\cdots ,N$。每堆石子有一定的质量 $m_i(m_i\le 1000)$。现在要将这 $N$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

  解析：设$dp[i][j]$为合并区间$[i,j]$石子的最优解，则有$dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum);$代码如下：

  #include
  using namespace std;
  const int N=3e2+5;
  int n,a[N],dp[N][N];
  int main()
  {
  	cin>>n;
  	for(int i=1;i<=n;i++) cin>>a[i];
  	memset(dp,0x3f,sizeof(dp));
  	for(int i=1;i<=n;i++) dp[i][i]=0;
  	for(int l=2;l<=n;l++)
  		for(int i=1;i<=n-l+1;i++)
  		{
  			int j=i+l-1;
  			int sum=0;
  			for(int k=i;k<=j;k++) sum+=a[k];
  			for(int k=i;k

  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

  环形区间DP

  题目链接：石子合并

  题意：在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出一个算法,计算出将 $N$ 堆石子合并成 $1$ 堆的最小得分和最大得分。

  解析：断链成环，具体操作是将原数组复制成两倍，然后跟上题一样做区间$DP$即可，代码如下：

  #include
  using namespace std;
  const int N=205;
  int n,m,k;
  int a[N],dp[N][N],dp1[N][N],s[N];
  int main()
  {
  	cin>>n;
  	memset(dp,0x3f,sizeof(dp));
  	for(int i=1;i<=n;i++) cin>>a[i],a[n+i]=a[i];
  	for(int i=1;i<=2*n;i++) dp[i][i]=0,dp1[i][i]=0,s[i]=s[i-1]+a[i];
  	for(int len=1;len<=n;len++)
  	{
  		for(int i=1;i<=2*n-len+1;i++)
  		{
  			int j=i+len-1;
  			for(int k=i;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

  题目链接：能量项链

  题意：给你一项链，项链上有$n$颗珠子。相邻的两颗珠子可以合并(两个合并成一个)。合并的同时会放出一定的能量。不同的珠子的合并所释放的能量是不同的。问：按照怎样的次序合并才能使释放的能量最多？

  解析：根据区间$DP$的套路，易得状态转移方程为：$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]\ast a[k+1]\ast a[j+1]);$跟上题一样，断链成环，做一遍$DP$即可。代码如下：

  #include
  using namespace std;
  const int N=205;
  int n,m,k;
  int a[N],dp[N][N];
  int main()
  {
  	cin>>n;
  	for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];a[2*n+1]=a[1];
  	for(int i=1;i<=2*n;i++) dp[i][i]=0;
  	for(int l=2;l<=n;l++)
  		for(int i=1;i<=2*n-l+1;i++)
  		{
  			int j=i+l-1;
  			for(int k=i;k

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

区间DP的一些应用

题目链接：涂色

题意：假设你有一条长度为 $5$ 的木板，初始时没有涂过任何颜色。你希望把它的 $5$ 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 $5$ 的字符串表示这个目标：$\text{RGBGR}$。每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 $\text{RRRRR}$，第二次涂成 $\text{RGGGR}$，第三次涂成 $\text{RGBGR}$，达到目标。用尽量少的涂色次数达到目标。

解析：本题需要小小地贪心一些，当$s[i]==s[j]$时，要么让区间$[i,j-1]$刷$i$的时候多往右刷一格，要么让区间$[i+1,j]$刷$j$的时候多往左刷一格，这样不会产生更多的代价且多刷了一格，显然只会使得结果更优。不相等的话，只能裂开取最小值了。代码如下：

#include
using namespace std;
const int N=105;
int n,m,k;
int a[N],dp[N][N];
char s[N];
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int l=2;l<=n;l++)
        for(int i=1;i<=n;i++)
        {
            int j=i+l-1;
            if(s[i]==s[j]) dp[i][j]=min(dp[i][j-1],dp[i+1][j]);
            else
            {
            	for(int k=i;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

题目链接：248 G

题意：给定一个1*n的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问序列中出现的最大数字的值最大是多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。

解析：区间$DP$,裂开取最大值即可,注意需要满足两块相等才能合并。代码如下：

#include
using namespace std;
const int N=255;
int n,m,k;
int a[N],dp[N][N];
int main(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],dp[i][i]=a[i];
        for(int l=2;l<=n;l++)
                for(int i=1;i<=n-l+1;i++)
                {
                        int j=i+l-1;
                        for(int k=i;k

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

题目链接：字符串折叠

题意：折叠的定义如下：

1. 一个字符串可以看成它自身的折叠。记作 S = S

2. X(S)是 $X$ 个 S连接在一起的串的折叠。记作 X(S) = SSSS…S。

3. 如果 A = A’, B = B’，则 AB = A’B’ 。例如：因为 3(A) = AAA, 2(B) = BB，所以 3(A)C2(B) = AAACBB，而 2(3(A)C)2(B) = AAACAAACBB

给一个字符串，求它的最短折叠。

例如 AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

解析：考虑区间动态规划，先分类讨论，对于区间$[i,j]$对应的字符串可以不采用缩写的方式，那么有$dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);$

如果对区间$[i,j]$对应的字符串采用缩写的方式，那么枚举循环节，假设$[i,k]$对应的字符串是$[i,j]$对应的字符串的循环节，那么有

$dp[i][j]=min(dp[i][j],dp[i][k]+2+len);//2是括号长度再加数字长度 $ 代码如下：

#include
using namespace std;
const int N=105;
int n,m,k;
int a[N],dp[N][N];
string s;
int main(){
    cin>>s;
    n=s.size();
    memset(dp,0x3f,sizeof(dp));
    s="0"+s;
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int l=2;l<=n;l++)
        for(int i=1;i<=n-l+1;i++)
        {
            int j=i+l-1;
            for(int k=i;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