河南网站平台建设公司,wordpress文章设置仅会员可见,天河网站建设系统,深圳小型网站建设这里写目录标题 cpp 101 最长回文子串1.1 题目1.2 思路1.3 程序实现 2 买卖股票的最好时机(一)2.1 题目2.2 思路2.3 程序实现2.4 程序实现 – 优化 3 [NOIP2002 普及组] 过河卒3.1题目3.2 思路3.3程序实现 – dp 4 题目链接 cpp 10
1 最长回文子串
1.1 题目 1.2 思路
读完了… 这里写目录标题 cpp 101 最长回文子串1.1 题目1.2 思路1.3 程序实现 2 买卖股票的最好时机(一)2.1 题目2.2 思路2.3 程序实现2.4 程序实现 – 优化 3 [NOIP2002 普及组] 过河卒3.1题目3.2 思路3.3程序实现 – dp 4 题目链接 cpp 10
1 最长回文子串
1.1 题目 1.2 思路
读完了题知道在一个长度为n的字符串中求最长回文子串的长度。回文子串可以理解为对称的字符串。因为具有对称性那么基本思路就是“中心扩展法”也就是依次字符串然后遍历到该字符就向其两边扩展如果两边的字符相等那么就记录到retlen变量中遍历完最后得到最大长度返回即可。为了方便理解画个图 此外分析示例还得注意奇数偶数的区别那么接下来就是程序实现。
1.3 程序实现
首先按照思路分析的“中心扩展法”遍历字符串且从i处从中心站展开依次求得的retlen,与retlen不断比较更新然后又因为需要区分奇数和偶数的情况所以分别求得最大值最后再比较依次得到最终最大的retlen返回即可。
class Solution
{
public:int getLongestPalindrome(string A){size_t len A.size();int left 0;int right 0;int retlen 0;//偶数for(int i 0;i len; i){left i;right i 1;while(left 0 right len A[left] A[right]){left--;right;}retlen max(retlen ,right - left - 1);}//奇数for(int j 0;j len;j){left j;right j;while(left 0 right len A[left] A[right]){left--;right;}retlen max(retlen ,right - left - 1);}return retlen ;}
}; 2 买卖股票的最好时机(一)
2.1 题目 2.2 思路
读完题知道对于一组股票的买卖机制只能买卖一次让求得获得的利润的最高收益如果无论什么时候买入卖出都是亏不管亏多少即没有利润则输出0即可。那么基本思路就是枚举/蛮力法求得每一组的利润差返回最大值尝试过后发现两层for会超时此题限制1ms解决。因此需要在蛮力法基础上优化所以蛮力法也写一写然后基于蛮力法回溯重复了太多次进行优化思考发现如果我们反过来逆向思维先考虑卖出的价值然后就只需要求得该卖出点之前的最小价值即可得到的差就是最大差也就是说只需要遍历一遍即可。接下来就是程序实现。
2.3 程序实现
首先根据蛮力法思路分析依次枚举所有情况求得最大差值输出即可此题会超时。所以得进行优化。
#include iostream
using namespace std;const int N 1e5 10;int arr[N];int main()
{int n;cin n;for(int i 0;i n;i)cin arr[i];int maxval 0;for(int i 0;i n; i){for(int j i;j n;j){maxval max(maxval , arr[j]- arr[i]);}}cout maxval endl;return 0;
} 2.4 程序实现 – 优化
基于上述的蛮力法进行优化为了方遍理解根据思路分析画个演示图 那么程序实现按照要求写好输入然后定义minval初始化arr[0]当作假设的最小值进行遍历比较更新即可再定义一个maxSub表示遍历至 i 位置时与minval的最大差值值得注意的是遍历时注意minval和maxSub的顺序性先求最小值minval再求maxSub即可。
#include iostream
#include vector
using namespace std;int main()
{int n 0;cin n;vectorint arr(n);int m 0;while(n--){cin arr[m];m;}int minval arr[0];int submax 0;for(int i 0;iarr.size();i){minval min(arr[i],minval);submax max(submax, arr[i] - minval);}cout submax endl;return 0;
} 3 [NOIP2002 普及组] 过河卒
3.1题目 3.2 思路
读完题知道让求从A点按照一定的规则走到B点最多有多少条的路径。分析题目需要知道按照一定的规则可以向右或向下走就想到了动态规划dp思路然后题目中还需要注意的是马的控制点不能被走(访问)也就是象棋中马在坐标上走的斜日所设计的点且包括马的起始点都被称为控制点。其中马是一开始就给出的固定点(x,y)且题目也给了马跳跃点与马起始点的关系。此外还得注意的是根据示例和棋盘得知棋盘的大小是(n1)(m1)。 所以综合所述思考分析得出 (1)、可使用动态规划dp思路解题; (2)、马的控制点除了斜“日”外还包括自身的起始位置 (3)、棋盘的大小是(n1)(m1). 所以分析了注意点后那么就回归到动态规划的dp状态表示和状态转移方程上来 由题目的走的规则定义dp[i][j]状态表示走到该位置最多有几条路径 推导状态转移方程dp[i][j] d[i][j-1] d[i-1][j] ; 此外注意如果B点起始位置就与马的起始位置或控制点重合还有就是B点的上方和左方全部被阻塞即是控制点那么以上极端情况此时dp[i][j] 0; 那么接下来就是程序实现。
3.3程序实现 – dp
首先根据思路的分析写好输入定义开辟好dp数组(两个坑点稍后说)根据棋盘的大小为了坐标能够统一描述所以这里就额外多开辟一行一列那么x和y就需要映射坐标1即可然后探究dp的初始化问题画个图更清晰 接着实际二维数组就从[1n1]和[1m1]遍历不断判断极端情况的处理即可最后输出dp[n1][m1]即可。到此思路没有问题总结步骤为一下几点 (1)、映射x和y的坐标; (2)、根据(多开辟一层)数组定义初始化dp[0][1] 1 或 dp[1][0] 1均可; (3)、遍历二位数组注意边界控制从[1n1]和[1m1]遍历; a、判断极端情况1.马的控制点阻塞路径 2.重合问题; b、正常执行状态转移方程dp[i][j] d[i][j-1] d[i-1][j] ; (4)、最后输出dp[n1][m1]即可. 另外上面提到的两个坑点在于我写好后提交不通过发现数据超范围了所以最好使用long long开辟数组还有一个坑点是在于开辟的大小范围由于多开辟的一层使用所以这里至少大于等于22才行。之前使用dp[21][21]无法通过所有用例哈。
#include iostream
using namespace std;long long dp[22][22];int main()
{int n,m,x,y;cin n m x y;//映射坐标x 1;y 1;//初始化dp[0][1] 1;//遍历for(int i 1;i n1; i){for(int j 1;j m1; j){//极端情况的处理: 1.马控制点 2.自身重合if((i ! x j ! y abs(i - x) abs(j - y) 3) || (i x j y)){dp[i][j] 0;}else{dp[i][j] dp[i][j-1] dp[i-1][j];}}}cout dp[n1][m1] endl;return 0;
} 4 题目链接
最长回文子串 买卖股票的最好时机(一) [NOIP2002 普及组] 过河卒
