• 动态规划--区间dp

    区间dp

    题目列表：

    (1)石子合并

    在复习石子合并之前，为了直接进入专题“区间dp“，做一个区间dp的基础题，这个题目具有代表性：(题目用到了前缀和，前缀和看这里： ）

    1. 使用了区间dp的模板
    2. 清晰理解区间dp的思想

    区间dp：将问题分为若干区间，不断解决小区间，最终延展到整个问题的区间，即：一个问题的范围是一个很大的区间，那么通过不断解决小区间，延伸到解决大区间
    在这里插入图片描述

    #include
#include
#include
using namespace std;

const int N = 310,INF=0x3f3f3f3f;

int f[N][N];  //f[i][j]表示区间i到j的石子合并的最小代价。那么最终问题的解就是f[1][n]表示第一个石子到最后一个石子合并的最小代价
//dp问题三部曲：
//（1）集合定义，即dp[i][j]表示什么，是否合理  （2）dp初始化，由于dp要往后面推，那么dp就要有初始值，0生1，1生2，3生3，3生万物
//（3）dp的状态转移，即当前dp的下一步要解决什么事情（也叫状态转移方程组）

int w[N];  //存储石子的重量
int pre[N];   //石子堆的前缀和
int n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> w[i];
		pre[i] = pre[i - 1] + w[i];
	}
		

	for (int i = 1; i <= n; i++)
		f[i][i] =0;      //区间为1的石子无法合并，所以消耗的体力就是0

	for (int len = 2; len <= n; len++)  //枚举区间长度
	{
		for (int L = 1; L + len - 1 <= n; L++)//(L+len-1)表示长度为len的区间的右端点
		{
			int R = L + len - 1;     //右端点
			f[L][R] = INF;  //因为要求最小值，先预先设置一个最大值
			for (int k = L; k <R; k++)   //将当前长度区间分为两个部分，求两个部分的最小值（因为区间合并的最后一步就是将两个石子堆合并为一个石子堆）
			{
				f[L][R] = min(f[L][R], f[L][k] + f[k + 1][R] + pre[R] - pre[L - 1]); //f[L][R]的最小价值等于两个部分的最小值加上整个区间的重量
			}
		}
	}
	cout << f[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

    (2)环形石子合并

    在这里插入图片描述

    这题于上一个题的唯一区别在于：这是环形，首尾的石子可以先合并。那么就使用一种”化曲为直“的思想。将环形结构拉直变成线性结构：
    将数组扩大两倍，后面部分复制一遍数据即可模拟环形结构。

    #include
#include
#include
using namespace std;

const int N = 410,INF=0x3f3f3f3f;

int f[N][N];   //f[i][j]表示区间[i,j]的石子合并消耗的最小体力。
int g[N][N];   //g[i][j]表示区间[i,j]的石子合并消耗的最大体力
int pre[N];   //pre[i]表示前i个石子的重量和
int w[N];   //石子重量   
int n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> w[i];
	for (int i = n + 1; i <= 2 * n; i++)  //化曲为直的操作
		w[i] = w[i - n];
	for (int i = 1; i <= 2 * n; i++)
	{
		pre[i] = pre[i - 1] + w[i];
	}

	//初始化
	for (int i = 1; i <= n * 2; i++)
		f[i][i] = g[i][i] = 0;

	for (int len = 2; len <= n; len++)
	{
		for (int l = 1; l + len - 1 <= 2 * n; l++)
		{
			int r = l + len - 1;
			f[l][r] = INF;   //求最小值给最大值
			g[l][r] = -INF;   //求最大值给最小值
			for (int k = l; k < r; k++)
			{
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + pre[r] - pre[l - 1]);
				g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + pre[r] - pre[l - 1]);
			}
		}
	}
	int res = INF; 
	int ans = -INF;
	for (int i=1; i + n - 1 <= 2 * n; i++)
	{
		res = min(res, f[i][i + n - 1]);
		ans = max(ans, g[i][i + n - 1]);
	}
	cout << res <<endl<< ans;
	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

    (3)能量项链

    在这里插入图片描述
    大致题意：
    每个珠子都有两面，一面一个值。有n个珠子，首尾相连，且任意相邻的两个珠子的邻接面的值是一样的，两颗珠子可以合并为一个珠子，且释放能量。
    给一个示例：

    （1，2） （2，3）（3，4）（4，1） 4颗珠子，首尾相连且满足相邻的值一样。有点像矩阵相乘
    其中一种组合方法：
    （1，2）和（2，3）组合变成(1,3),释放能量1x2x3
    （1，3）和（3，4）组合变成(1,4),释放能量1x3x4
    （1，4）和（4，1)组合变成(1,1)，释放能力1x4x1
    没有珠子可以合并了，发现一共合并3次，释放能量：6+12+4=22.但是不是最优解就不知道了。因为从不同的珠子为起点来合并答案都不一样.

    #include
#include
#include
using namespace std;

const int N=1100,INF=0x3f3f3f3f;
typedef long long ll;
ll f[N][N];   //f[i][j]表示区间[i,j]的石子合并的最大能量,最后的答案是f[1][n+1]
int w[N*2];
int n;


int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        w[i+n]=w[i];
    }
    
    //dp初始化
    for(int i=1;i<n*2;i++)   //长度为2的区间代表一个石子，不能合并，从定义出发那就意味着没有能量。
        f[i][i+1]=0;
    
    for(int len=3;len<=n+1;len++) //枚举长度，什么是n+1，因为3个石子的区间长度是4
    {
        for(int l=1;l+len-1<=n*2;l++)  //枚举左端点
        {
            int r=l+len-1;  //右端点
            f[l][r]=-INF;
            for(int k=l+1;k<r;k++)  //区间分段求最大，分段要注意细节，根据事实来分,这里的细节是：长度为1的区间没有意义  2 3 4 5
            {
                f[l][r]=max(f[l][r],f[l][k]+f[k][r]+w[l]*w[r]*w[k]);
            }
        }
    }
    
    
    ll res=0;
    for(int i=1;i+n<=2*n;i++)  //枚举左端点求最大值
    {
        res=max(res,f[i][i+n]);  //搞不清这个是n还是n+1的时候举个例子。比如n==3，  1 2 3 1 2 3.要选取4个数,保证首尾相同
    }
    cout<<res;
    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

    (4)加分二叉树

    在这里插入图片描述

    #include
#include
#include
using namespace std;

const int N=50,INF=0x3f3f3f3f;

int w[N];
int f[N][N];  //f[i][j]表示区间[i,j]的子树的最大值
int path[N][N];  //path[i][j]表示子树[i,j]的根节点

int n;


void dfs(int l,int r)  //求前序遍历
{ 
    if(l>r)return;
    int k=path[l][r];
    printf("%d ",k);
    dfs(l,k-1);
    dfs(k+1,r);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i];
        
    //初始化
    for(int i=1;i<=n;i++)
    {
        f[i][i]=w[i];   //一个节点的最大能量就是当前节点值
        path[i][i]=i;  //叶子节点没有子树，的根节点就是自己
    }
    
    //dp的思路是：枚举所有长度的子树，且求出字典序最小的根节点
    for(int len=1;len<=n;len++)   //枚举长度
    {
        for(int l=1;l+len-1<=n;l++)  //枚举左端点
        {
            int r=l+len-1;  //右端点
            f[l][r]=-INF;
            for(int root=l;root<=r;root++)  //枚举根节点
            {
                int left=root==l?1:f[l][root-1];
                int right=root==r?1:f[root+1][r];
                int temp=left*right+w[root];
                if(l==r)
                    temp=w[root];
                if(temp>f[l][r])  //因为原先的树是12345，所以保证字典序的最小就是保证每次的根节点最小就好了。因为四前序遍历
                {
                    f[l][r]=temp;
                    path[l][r]=root;
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    dfs(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
    • 61

    (5)凸多边形的划分

    在这里插入图片描述
    这个题目不用高精度只能过几个点，所以用高精度
    先上一个不用高精度的，能过三个数据：

    #include
#include
#include
#include
using namespace std;

const int N = 100,INF=0x3f3f3f3f;

long long int f[N][N];  //f[i][j]表示区间[i,j]的权值最大值
int w[N];    //每个点的权值
int n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> w[i];

	//初始化
	for (int i = 1; i <n; i++)  //两个点不能连接三角形，所以权值为0
		f[i][i + 1] = 0;
	for (int len = 3; len <= n;len++)  //枚举区间   ,,为什么不要做环形处理，要看定义，这里的定义是区间[i,j]内划分三角形的最大价值
		for (int l = 1; l + len - 1 <= n; l++)  //枚举左端点
		{
			int r = l + len - 1;
			if (len == 3)
			{
				f[l][r] = w[l] * w[l+1] * w[r];
				continue;
			}
			f[l][r] = INF;
			for (int k = l + 1; k < r; k++)
			{
				f[l][r] = min(f[l][r], f[l][k] + f[k][r]+w[l]*w[r]*w[k]);
			}
		}
	cout << f[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

    下面是高精度：

    #include
#include
#include
#include
#include

using namespace std;
typedef long long ll;
const int N=51,M=35,INF=0x3f3f3f3f;

vector<int>f[N][N];  //状态表示：f[i][j]表示一个一个一维数组，存放一个高精度的值，他的意义是左端点是i，右端点是j的封闭的多边形的最大价值
int w[N];   //存储点
int n;


void pre(vector<int>& s,int t)   //先假设一个数，边看这个数边来模拟就不容易出错。example:1234
{
    //将t放入s
    while(t)
    {
        s.push_back(t%10);
        t/=10;
    }
}

bool cmp(vector<int>&a ,vector<int>&b)  //比较f[l][r]和f[l][k]+f[k][r]+w[l]*w[k]*w[r]哪个小,规定a>b,返回true
{
    if(a.size()!=b.size())
    {
        if(a.size()>b.size())
            return true;
        else
            return false;
    }
    else
    {
        //说明两个数组长度一样
        for(int i=a.size()-1;i>=0;i--)  //逆序比较
        {
            if(a[i]!=b[i])  //高位比较，如果a[i]大于b[i]，则a>b
                return a[i]>b[i];
        }
        return true;//相等的情况
    }
      
}

vector<int> mul(vector<int>&a,ll b)//123 12
{
    vector<int>c;
    ll t=0;
    for(int i=0;i<(int)a.size();i++)
    {
        t+=b*a[i];
        c.push_back(t%10);
        t/=10;
    }
    while(t)
    {
        c.push_back(t%10);
        t/=10;
    }
    return c;
}

vector<int>add(vector<int>&a,vector<int>&b)
{
    vector<int>c;
    ll t=0;
    for(int i=0;i<a.size()||i<b.size();i++)
    {
        if(i<a.size())t+=a[i];
        if(i<b.size())t+=b[i];
        c.push_back(t%10);
        t/=10;
    }
    while(t)
    {
        c.push_back(t%10);
        t/=10;
    }
    return c;
    
    
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    //初始化dp,dp[i][i+1]=0,因为两条边是不能构成回路的，多边形必须要3条边或者说3个点才可以构成回路
    vector<int>temp;
    for(int len=3;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)  //枚举左端点
        {
            int j=i+len-1;  //右端点
            //因为要求f[l][r]的最小值,所以将其先预先设置为无穷大，
            f[i][j]=vector<int>(M,9);
        
            for(int k=i+1;k<j;k++)  //k能枚举到i+1到j-1，
            {
                //目的是求f[i,k]+f[k,j]+w[i]*w[k]*w[j];
                //先求乘法
                temp.clear();
                temp.push_back(w[i]);  //高精度相加，那么是3个数组的加法，需要将具体的数字都放在数组里面，先将第一个数放在数组里面
                //cout<
                temp=mul(temp,w[k]);
                temp=mul(temp,w[j]);   //到这里就完成了乘法了
                temp=add(temp,f[i][k]);
                temp=add(temp,f[k][j]);
                //到这里就完成了加法和乘法的累和
                if(cmp(f[i][j],temp))  //如果temp小于等于f[i][j]
                    f[i][j]=temp;
            }
            
        }
    }
    for(int i=f[1][n].size()-1;i>=0;i--)
        cout<<f[1][n][i];
    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
    • 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
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122

    (6)棋盘分割

    记忆化dp，将棋盘进行分割，分别有两种情况。要么竖着切，要么横切。
    然后取一边继续切割。最后回溯的时候取两边的最小值即可

    #include
#include
#include
#include
using namespace std;

const int N=16;
double f[N][N][N][N][N];  //f[k][x1][y1][x2][y2]表示对棋盘进行了k次划分，得到的左上角是(x1,y1),右下角是(x2,y2)的棋盘的最小分值

int n,m=8;
int s[N][N];  //前缀和
double x;

double get(int x1,int y1,int x2,int y2)
{
    double delta=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];  //计算当前矩阵的分值和
    delta=delta-x;
    return delta*delta;
}


double dp(int k,int x1,int y1,int x2,int y2)
{
    if(f[k][x1][y1][x2][y2]>=0)return f[k][x1][y1][x2][y2];  //记忆化搜索的关键
    if(k==n) return f[k][x1][y1][x2][y2]=get(x1,y1,x2,y2);   //最后一次不需要继续切了，直接返回当前的矩阵
    
    double t=1e9;  
    for(int i=x1;i<x2;i++)  //横切
    {
        t=min(t,dp(k+1,x1,y1,i,y2)+get(i+1,y1,x2,y2));  //取上半部分继续切，那么下半部分分值加起来
        t=min(t,dp(k+1,i+1,y1,x2,y2)+get(x1,y1,i,y2));
    }
    
    for(int i=y1;i<y2;i++)  //竖切
    {
        t=min(t,dp(k+1,x1,y1,x2,i)+get(x1,i+1,x2,y2));  //取左边继续切
        t=min(t,dp(k+1,x1,i+1,x2,y2)+get(x1,y1,x2,i));
    }
    return f[k][x1][y1][x2][y2]=t;
}


int main()
{
    cin>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&s[i][j]);
    for(int i=1;i<=m;i++)   //二维前缀和
        for(int j=1;j<=m;j++)
            s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    
    memset(f,-1,sizeof f);
    x=(double)s[m][m]/n;
    printf("%.3lf",sqrt(dp(1, 1, 1, m, m) / 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

    好了，区间dp到此为止。明天树形dp见。

  • 相关阅读:
    【系统分析师之路】第五章 复盘软件工程（软件过程改进）
    【C++】day3学习成果：类
    华朗复读衔接营励志开营！全名师阵容护航 解读高考成功秘钥
    【前端开发---Vue3】前段开发之详细的Vue3入门教程，特别适合小白系统学习，入门到熟练使用Vue看这一篇就够了！
    Unity3D学习笔记12——渲染纹理
    【完美世界】石昊偷渡出境四人组产生分歧，云曦和石昊牵手，二人世界要开始了
    宝宝餐椅儿童商品认证和ASTM F404检测标准的重要性
    基于MindSpore框架的道路场景语义分割方法研究
    stm32f407探索者开发板（二）——新建工程（基于固件库）
    致谢每一位ChunJun Contributor！这里有一份礼物等你领取！
  • 原文地址：https://blog.csdn.net/m0_60343477/article/details/127897346