旧作补档

2022-04-16

前言

快考蓝桥杯了，发现自己dp不会，补了几题。
写一篇题解攒攒人品以防爆零

题目描述

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。
第一行有 2 个用空格隔开的整数 m 和 n，表示学生矩阵有 m 行 n 列。
接下来的 m 行是一个 m×n 的矩阵，矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度，每行的 n 个整数之间用空格隔开。

样例

算法1

(dp) $O(n^2 m^2)$

C++ 代码

//来回传纸条和从起点传两次到终点是等价的，建模成从起点传两次到终点更好写
//dp[i][j][k][l]表示第一次传到(i,j)、第二次传到(k,l)时好心程度的最大值
//显然第一次传到(i,j)的最大值可以从(i-1,j)、(i,j-1)的最大值得来
//第二次传到(k,l)的最大值可以从(k-1,j)、(k,j-1)的最大值得来
//所以dp[i][j][k][l]的值是max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])+a[i][j]+a[k][l];(两种转移方式的组合的最大值再加上两个格子上的值)
//需要注意的是i==k&&j==l时，此时两个纸条到了同一格子上，但是每个格子上的好心值只能计算一次，所以要减去重复的
//最后结果根据dp的定义是dp[n][m][n][m]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 51;
int dp[N][N][N][N],a[N][N],m,n;
int main()
{
    cin >> n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cin >> a[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for (int j = 1; j <=m; j ++ )
        {
            for(int k=1;k<=n;k++)
            {
                for(int l=1;l<=m;l++)
                {
                    dp[i][j][k][l]=max(dp[i-1][j][k-1][l],max(dp[i-1][j][k][l-1],max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])))+a[i][j]+a[k][l];
                    if(i==k&&j==l)
                        dp[i][j][k][l]-=(a[i][j]+a[k][l]);
                }
            }
        }
    }
    cout << dp[n][m][n][m]<<endl;
    return 0;
}

Markdown笔记2

2022-04-14

段落

一个 Markdown 段落是由一个或多个连续的文本行组成，它的前后要有一个以上的空行（空行的定义是显示上看起来像是空的，便会被视为空行。
Markdown 段落没有特殊的格式，直接编写文字就好，段落的换行是使用两个以上空格加上回车。

段落换行示例

这是第一段的第一行  

这是第一段的第二行  

这是第二段的第一行  

这是第二段的第二行

最终效果如下：

这是第一段的第一行
这是第一段的第二行

这是第二段的第一行
这是第二段的第二行

字体

可以使用以下字体

字体示例

*斜体文本*
_斜体文本_
**粗体文本**
__粗体文本__
***粗斜体文本***
___粗斜体文本___

效果如下：
斜体文本
_斜体文本_
粗体文本
粗体文本
粗斜体文本
_粗斜体文本_

注意事项

Markdown 应用程序在如何处理单词或短语中间的下划线上并不一致。为兼容考虑，在单词或短语中间部分加粗的话，请使用星号（asterisks）。
Markdown 应用程序在处理单词或短语中间添加的下划线上并不一致。为了实现兼容性，请使用星号将单词或短语的中间部分加粗并以斜体显示，以示重要。
要同时用粗体和斜体突出显示文本，请在单词或短语的前后各添加三个星号或下划线。要加粗并用斜体显示单词或短语的中间部分，请在要突出显示的部分前后各添加三个星号，中间不要带空格。

例如：

1
2
3

Love**is**bold √    Love__is__bold ×  
A*cat*meow √    A_cat_meow ×
This is really***very***important text. √    This is really___very___important text. ×

实际效果
Loveisbold √ Loveisbold ×
Acatmeow √ A_cat_meow ×
This is reallyveryimportant text. √ This is really_very_important text. ×

Markdown笔记1

2022-04-14

标题

Markdown 支持两种标题的语法，类 Setext 和类 atx 形式。
类 Setext形式使用 = 和 - 标记一级和二级标题；类 Atx 形式则是在行首插入 1 到 6 个 # ，对应到标题 1 到 6 阶。

类 Setext形式示例

一级标题
=================

二级标题
-----------------

效果如下所示：

一级标题

二级标题

类 Atx 形式示例

# h1
## h2
### h3
#### h4
##### h5
###### h6

效果如下所示：

h1

h2

h3

h4

h5

h6

小技巧

VSCode 可以用Ctrl+Shift+V快捷键来对md文件进行预览
不同的 Markdown 应用程序处理 # 和标题之间的空格方式并不一致。为了兼容考虑，请用一个空格在 # 和标题之间进行分隔。

参考资料与文献

1、https://www.w3cschool.cn/markdownyfsm/ysu1e1.html

2、https://www.runoob.com/markdown/md-paragraph.html

3、https://markdown.com.cn/cheat-sheet.html

个人简介

2022-04-13

个人背景

　　某普通一本海洋专业大二学生，前蓝桥杯选手，数理和计算机基础基本没有的蒟蒻。

开通博客的目的

　　主要还是因为自己平时实在太颓了，想利用这个博客记录自己的一些学习日常以及整理一些知识（顺便学习前端，防止自己变得更颓）。

　　这个博客主要分享一些基础的算法（太难的我也不会奥），难度大概在洛谷提高以下；以及一些数学建模的常见模型和习题解答；还有一些前端的知识；以及杂文若干。(ps:本人刚刚学习如何维护博客，做的不好的地方请见谅)

My Blog

前言