算法竞赛备赛进阶之区间DP训练

区间动态规划(Interval Dynamic Programming,简称 IDP)是一种动态规划算法,用于解决包含区间状态的优化问题。在区间动态规划中,问题可以划分为多个不重叠的区间,每个区间可以独立求解,并且状态在相邻区间之间是独立的。

区间动态规划的基本思想是将原问题转化为一系列子问题,每个子问题只涉及一个区间,然后使用动态规划算法求解每个子问题。在求解每个子问题的过程中,可以使用状态转移方程来更新区间状态。

下面是一个简单的例子,说明如何使用区间动态规划求解区间和问题。假设给定一个整数数组 nums 和一个整数 m,要求找到一个连续的子数组,使得该子数组的和不超过 m,并且该子数组的长度最大。

int maxSubArrayLen(int m, int n, int* nums)
{    
    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 0;    
    for (int i = 1; i <= n; i++)
    {        
        for (int j = 0; j <= m; j++)
        {            
            if (i == 1) 
            {                
                dp[i][j] = dp[i-1][j];
            } 
            else
            {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1]);
            }
        }
    }
    return dp[n][m];
}

在这个例子中,我们使用二维数组 dp 来保存状态,其中 dp[i] [j] 表示在前 i 个元素中选择不超过 j 的最大和。初始状态为 dp[0] [0] = 0。然后我们使用两个嵌套的循环来遍历所有可能的状态,对于每个状态,我们可以使用状态转移方程来更新它。最后返回 dp[n] [m] 即可得到最大和不超过 m 的最长子数组的长度。

需要注意的是,在实际应用中,需要根据具体问题来设计状态转移方程和初始化状态。同时,还需要考虑如何处理边界条件和特殊情况。

1.环形石子

将n堆石子绕圆形操场排放,现在要将石子有序合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆,并且新的一堆石子数记作该次合并的得分。

请编写一个程序,读入堆数n及每堆的石子数,并进行如下计算:

输入格式

第一行包含整数n,表示共有n堆石子。

第二行包含n个整数,分别表示每堆石子的数量。

可以将数据变成两倍,从而实现所有的序列。

  1. 迭代式

    for(int len = 1;len <= n; len++)
        for(int L = 1;L + len - 1 <= n; L++)
            R = L + len - 1;

  2. 记忆化搜索

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 410, INF = 0x3f3f3f3f;
​
int n;
int s[N], w[N];
int f[N][N], g[N][N];
​
int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n; i++)
    {
        scanf("%d", &w[i]);
        w[i + n] = w[i];
    }
    
    for(int i = 1;i <= n * 2; i++) s[i] = s[i - 1] + w[i];
    
    memset(f, 0x3f, sizeof(f));
    memset(g, -0x3f, sizeof(g));
    
    for(int len = 1;len <= n; len++)
        for(int l = 1;l + len - 1 <= n * 2; l++)
        {
            int r = l + len - 1;
            if(len == 1)
                f[l][r] = g[l][r] = 0;
            else
            {
                for(int k = 1;k < r; k++)
                {
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                    g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l-1]);
                }
            }
        }
    
    int minv = INF, maxv = -INF;
    for(int i = 1;i <= n; i++)
    {
        minv = min(minv, f[i][i + n - 1]);
        maxv = max(maxv, g[i][i + n - 1]);
    }
    
    cout << minv << endl << maxv << endl;
    
    return 0;
}

2.能量项链

在 Mars 星球上,每个 Mars 人都随身佩带着一串能量项链,在项链上有 NN 颗能量珠。

能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。

并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。

因为只有这样,通过吸盘(吸盘是 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两颗珠子聚合后释放的能量为:(4⊕1)=10×2×3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710。

输入格式

输入的第一行是一个正整数 N,表示项链上珠子的个数。

第二行是 N 个用空格隔开的正整数,所有的数均不超过 1000,第 i 个数为第 i 颗珠子的头标记,当 i<N 时,第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记,第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。

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

#include<cstring>
#include<algorithm>
#include<iostream>
​
using namespace std;
​
const int N = 210;
​
int n;
int w[N];
int f[N][N];
​
int main()
{
    cin >> n;
    for(int i = 1;i <= n; i++)
    {
        cin >> w[i];
        w[i + n] = w[i];
    }
    
    for(int len = 3;len <= n + 1; len++)
        for(int l = 1;l + len - 1 <= n * 2; l++)
        {
            int r = len + l - 1;
            for(int k = l + 1;k < r; k++)
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }
    
    int res = 0;
    for(int i = 1;i <= n; i++) res = max(res, f[i][i + n]);
    
    cout << res << endl;
    
    return 0;
}

3.凸多边形的规划

给定一个具有N个顶点的凸多边形,将顶点从1至N标号,每一个顶点的权重都是一个·正整数。

将这个多项式划分成N-2个互不相交的三角形,对于每个三角形,其三个顶点的权值相乘。

#include<iostream>
#include<algorithm>
​
using namespace std;
​
int n;
int w[N];
int f[N][N][M];
​
void add(LL a[], LL b)
{
    static LL c[M];
    memset(c, 0, sizeof(c));
    for(int i = 0, t = 0;i < M; i++)
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof(c));
}
​
void mul(LL, a[], LL b)
{
    static LL c[M];
    memset(c, 0, sizeof(c));
    LL t = 0;
    for(int i = 0;i < M; i++)
    {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, size(c));
}
​
int cmp(LL a[], LL b[])
{
    for(int i = 0;i < m; i++)
        if(a[i] > b[i]) return 1;
    else if(a[i] < b[i]) return -1;
    return 0;
}
​
void print(LL a[])
{
    int k = M - 1;
    while(k && |a[k]) k--;
    while(k >= 0) cout << a[k--];
    cout << endl;
}
​
int main()
{
    scanf("%d", &n)
    for(int i = 1;i <= n; i++)
        cin >> w[i];
    
    LL temp[M];
    for(int len = 3;len <= n; len++)
        for(int l = 1;l + len - 1 < n; l++)
        {
            int r = l + len - 1;
            f[l][r][M - 1] = 1;
            for(int k = l + 1;k < r; k++)
            {
                memset(temp, 0, sizeof(temp));
                temp[0] = w[l];
                mul(temp, w[k]);
                mul(temp, w[r]);
                add(temp, f[l][k]);
                add(temp, f[k][r]);
                if(cmp(f[l][r], temp) > 0)
                    memcpy(f[l][r], temp, sizeof(temp));
            }
        }
    
    print(f[1][n]);
    return 0;
}

4.加分二叉树

是一个n个节点的二叉树tree的中序遍历为(1,2,3,4,......,n),其中的数字1,2,3,4,......,n为节点。

每个结点都有一个分数(均为正整数),记作第i个节点的分数为d,tree及它的每一个子树都有一个加分,任意模子树subtree(也包含tree本身)的加分计算方法如下:

subtree的左子树的加分 * subtree的右子树的加分 * subtree的根的分数

若某个子树为空,规定其加分为1,叶子的加分就是叶结点本身的分数,不考虑它的空子树。

试求一棵符合中序遍历为(1,2,3,4,......,n)且加分最高的二叉树tree。

要求输出:

  1. tree的最高加分项

  2. tree的前序遍历

输入格式

第一行:一个整数n,为节点个数

第二行:n个用空格隔开的整数,为每个节点的分数(分数<100)

闫氏DP分析法

动态规划:

  1. 状态表示f[l,r]:

    1. 集合:所有中序遍历是[l,r]这一段的二叉树的集合

    2. 属性:max

  2. 状态计算:w[u] + tree[r] * tree[l]

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 30;
​
int n;
int w[N];
int g[N][N];
int f[N][N];
​
void dfs(int l, int r)
{
    if(l < r) return;
    
    int root = g[l][r];
    cout << root << ' ';
    dfs(l, root - 1);
    dfs(root + 1, r);
}
​
int main()
{
    cin >> n;
    for(int i = 1;i <= n; i++) cin >> w[i];
    
    for(int len = 1;len <= n; len++)
        for(int l = 1;l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            if(len == 1)
            {
                f[l][r] = w[l];
                g[l][r] = l;
            }
            else
            {
                for(int k = l;k <= r; k++)
                {
                    int left = k == l ? 1 : f[l][k - 1];
                    int right = k == r ? 1 : f[k + 1][r];
                    int score = left * right + w[k];
                    if(f[l][r] < score)
                    {
                        f[l][r] = score;
                        g[l][r] = k;
                    }
                }
            }
        }
    
    cout << f[1][n] << endl;
    dfs(1, n);
    
    return 0;
}

5.棋盘分割

将一个 8×8 的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了 (n−1) 次后,连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

1191_1.jpg

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。

现在需要把棋盘按上述规则分割成 n 块矩形棋盘,并使各矩形棋盘总分的均方差最小。

均方差

formula.png

,其中平均值

lala.png

,xi 为第 i 块矩形棋盘的总分。

请编程对给出的棋盘及 n,求出均方差的最小值。

输入格式

第 1 行为一个整数 n。

第 2 行至第 9 行每行为 8 个小于 100 的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

闫氏DP分析法

动态规划:

  1. 状态表示f[x1, y1, x2, y2]

    1. 集合:将子矩阵(x1, y1)(x2, y2)切分成k部分的所有方案

    2. 属性是

      formula.png

      最小值

  2. 状态计算

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
​
using namespace std;
​
const int N = 15, M = 9;
const double INF = 1e9;
​
int n, m = 8;
int s[M][M];
double f[M][M][M][M][N];
double x;
​
double get(int x1, int y1, int x2, int y2)
{
    double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] - s[x1 - 1][y1 - 1] -x;
    return sum * sum / n;
}
​
double dp(int x1, int y1, int x2, int y2, int k)
{
    int &v = f[x1][y1][x2][y2][k];
    if(v >= 0) return v;
    if(k == 1) return v = get(x1, y1, x2, y2);
    
    v = INF;
    for(int i = x1;i < x2; i++)
    {
        v = min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2));
        v = min(v, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2));
    }
    for(int i = y1;i < y2; i++)
    {
        v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2));
        v = min(v, dp(x1, i + 1, x2, y2, k - 1) + get(x1, y1, x2, i));
    }
    
    return v;
}
​
int main()
{
    cin >> n;
    for(int i = 1;i <= m; i++)
        for(int j = 1;j <= m; j++)
        {
            cin >> 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 = s[n][m] / n;
    
    printf("%.3lf\n", dp(1, 1, 8, 8, n));
    
    return 0;
}

子矩阵的和

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
​
using namespace std;
​
const int N = 15, M = 9;
const double INF = 1e9;
​
int n, m = 8;
int s[M][M];
double f[M][M][M][M][N];
double X;
​
double get(int x1, int y1, int x2, int y2)
{
    double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] - X;
    return sum * sum / n;
}
​
double dp(int x1, int y1, int x2, int y2, int k)
{
    double &v = f[x1][y1][x2][y2][k];
    if(v >= 0) return v;
    if(k == 1) return v = get(x1, y1, x2, y2);
    
    v = INF;
    for(int i = x1;i < x2; i++)
    {
        v = min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2));
        v = min(v, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2));
    }
    for(int i = y1;i < y2; i++)
    {
        v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2));
        v = min(v, dp(x1, i + 1, x2, y2, k - 1) + get(x1, y1, x2, i));
    }
    return v;
}
​
int main()
{
    cin >> n;
    for(int i = 1;i <= m; i++)
        for(int j = 1;j <= m; j++)
        {
            cin >> 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\n", sqrt(dp(1, 1, 8, 8, n)));
    
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/219908.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

分享126个图片JS特效,总有一款适合您

分享126个图片JS特效&#xff0c;总有一款适合您 126个图片JS特效下载链接&#xff1a;https://pan.baidu.com/s/1sOKHo4RciQXwQX9vhLIm3g?pwd6666 提取码&#xff1a;6666 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;收集整…

​CAN FD一致性测试:便捷、高效的自动化测试系统

后起之秀——CAN FD&#xff1a;随着各个行业的快速发展&#xff0c;消费者对汽车电子智能化的诉求越来越强烈&#xff0c;这使得整车厂将越来越多的电子控制系统加入到了汽车控制中&#xff0c;且在传统汽车、新能源汽车、ADAS和自动驾驶等汽车领域中也无不催生着更高的需求&a…

机器学习---朴素贝叶斯分类器的实现(对文本进行侮辱性言论和非侮辱性言论的分类)

1. loadDataSet函数 import numpy as np# 构造loadDataSet函数用于生成实验样本 def loadDataSet(): postingList[[my, dog, has, flea, problems, help, please],[maybe, not, take, him, to, dog, park, stupid],[my, dalmation, is, so, cute, I, love, him],[stop, postin…

JDK8升级11常见问题

JDK8升级11常见问题 1. 使用rt.jar/jce.jar情况 原代码&#xff1a; <plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-compiler-plugin</artifactId><configuration><source>1.8</source><targe…

计算机网络入侵检测技术研究

摘 要 随着网络技术的发展&#xff0c;全球信息化的步伐越来越快&#xff0c;网络信息系统己成为一个单位、一个部门、一个行业&#xff0c;甚至成为一个关乎国家国计民生的基础设施&#xff0c;团此&#xff0c;网络安全就成为国防安全的重要组成部分&#xff0c;入侵检测技术…

CUDA简介——For循环并行化

1. 引言 前序博客&#xff1a; CUDA简介——基本概念CUDA简介——编程模式 kernel相关语法定义为&#xff1a; kernel函数定义&#xff0c;与常规C函数定义类似。不同之处在于&#xff0c;有__global__关键字。 为说明符&#xff0c;告诉编译器该函数应编译运行在device上&a…

Understanding Computer Hardware

文章目录 I. Input Devices1. Keyboard&#xff08;1&#xff09;Layout&#xff08;2&#xff09;Key Types&#xff08;3&#xff09;Functionality&#xff08;4&#xff09;Connectivity&#xff08;5&#xff09;Ergonomics&#xff08;6&#xff09;Multimedia Keys&…

伯俊软件CTO陈雨陆:R3全渠道业务中台的OceanBase落地实践

11 月 16 日&#xff0c;OceanBase 在京顺利举办 2023 年度发布会&#xff0c;正式宣布&#xff1a;将持续践行“一体化”产品战略&#xff0c;为关键业务负载打造一体化数据库。其中&#xff0c;“数字化转型升级实践专场”我们有幸邀请到伯俊软件 CTO 陈雨陆进行《OceanBase …

java easyPOI导出一对多数据,设置边框,字体,字体大小

java easyPOI导出一对多数据&#xff0c;设置边框&#xff0c;字体&#xff0c;字体大小 需求总是千奇百怪&#xff0c;解决的方式也可以是多种多样。 今天碰到导出excel是一对多结构的&#xff0c;以往导出的数据都是一条一条的&#xff0c;所以采用的是比较方便简单的方法eas…

全网最新最全面的Appium自动化:Appium常用操作之设备操作

设备基本操作 前置条件&#xff1a; 示例代码&#xff1a; from appium import webdriver # 导入appium 驱动包 # 1、定义一个DesiredCapabilities配置的字典 des {automationName:appium,platformName:Android, # 平台的名称&#xff0c;iOS,Android,FirefoxOSplatformV…

打开游戏提示缺少(或找不到)XINPUT1_3.DLL怎么解决

在电脑使用过程中&#xff0c;我们可能会遇到一些错误提示&#xff0c;其中之一就是xinput1_3.dll丢失。那么&#xff0c;xinput1_3.dll是什么文件&#xff1f;它对电脑有什么影响&#xff1f;本文将详细介绍xinput1_3.dll丢失的原因以及五个详细的解决方法&#xff0c;帮助大家…

初识Protobuf与Protobuf的安装

目录 一、Protobuf 1.回顾序列化 2.Protobuf的特性 3.Protobuf的下载 ①ProtoBuf 在 window 下的安装 ②ProtoBuf 在 Linux 下的安装 一、Protobuf 1.回顾序列化 我们在先前的学习中也遇到过序列化。所谓序列化我的理解是&#xff0c;将复杂的对象以特定的方式转换以便于…

vue3-vite-ts:编写Rollup插件并使用 / 优化构建过程

一、vue3-vite-ts项目&#xff0c;编写Rollup插件并使用的意义 在使用Vue3 Vite TypeScript这种技术栈时&#xff0c;可以使用Rollup插件来优化构建过程&#xff0c;例如使用rollup-plugin-typescript2插件来编译TypeScript代码&#xff0c;使用rollup-plugin-vue插件来处理…

go-fastfds部署心得

我是windows系统安装 Docker Desktop部署 docker run --name go-fastdfs&#xff08;任意的一个名称&#xff09; --privilegedtrue -t -p 3666:8080 -v /data/fasttdfs_data:/data -e GO_FASTDFS_DIR/data sjqzhang/go-fastdfs:lastest docker run&#xff1a;该命令用于运…

基于深度学习YoloV8的火焰烟雾检测系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介简介YoloV8模型火焰烟雾检测系统模型训练实时检测 应用领域 二、功能三、系统四. 总结 一项目简介 # 基于深度学习YoloV8的火焰烟雾检测系统介绍 简介 深…

【Unity3D】Android打包报错AAPT2:xxx Linkxxx

Gradle Plugin 与Gradle版本不匹配问题 或 相关依赖库下载不完全问题&#xff1b; 使用镜像即可解决 也可以离线&#xff08;离线过于复杂 你能找到方法那最好是离线Maven) 仓库服务 找最新可用的镜像url&#xff0c;替换google()和jcenter()&#xff0c; 可以直接使用publ…

StoneDB-8.0-V2.2.0 企业版正式发布!性能优化,稳定性提升,持续公测中!

​ 11月&#xff0c;StoneDB 新版本如期而至&#xff0c;这一个月来我们的研发同学加班加点&#xff0c;持续迭代&#xff1a;在 2.2.0 版本中&#xff0c;我们针对用户提出的需求和做出了重量级更新&#xff0c;修复了一些已知和用户反馈的 Bug&#xff0c;同时对部分代码进行…

如何计算光伏电站的发电量?

光伏电站的发电量是衡量其性能和经济效益的关键指标。准确地预测和计算光伏电站的发电量对于投资决策、系统设计和优化至关重要。以下是一些计算光伏电站发电量的主要步骤和方法&#xff1a; 1、确定光伏电站的规模和配置 了解光伏电站的组件数量、类型、功率等级以及安装位置…

Win10点关机后马上又进入桌面解决方法

Win10点了关机&#xff0c;马上闪一下就又重新进入了桌面&#xff0c;关不了机怎么办&#xff1f;强制关机虽然是可行&#xff0c;但不能每一次都强制关机。下面给大家带来的win10不能关机的解决方法&#xff0c;希望能帮助到大家。 速印机&#xff08;理想、荣大等&#xff09…

用php和mysql制作一个网站

当使用PHP和MySQL制作网站时&#xff0c;我们可以利用PHP的强大功能来与MySQL数据库进行交互&#xff0c;从而实现动态网页的创建和数据存取。下面是一个关于如何使用PHP和MySQL制作网站的简单说明&#xff0c;以及一些示例代码。 ​ 1、R5Ai智能助手 chatgpt国内版本 :R5Ai智…