6.倒置字符串

之前用C实现过，真的不好理解，很绕

但是这次用C++

oj最好不要cin>>s，其中s是一个字符串，用getline函数

#include
#include
#include
#include
using namespace std;int main1()
{string s1;while (getline(cin, s1)){reverse(s1.begin(), s1.end());//将整个句子逆置auto start = s1.begin();for (int i = 0;s1.begin()+i!=s.end()+1; i++)//可能不会直接到end(){if (s1[i] == ' '){auto end = s1.begin() + i;reverse(start, end);//将每个单词逆置回来,逆置空格前的字符串start = end + 1;//跳过空格进入下一个单词}if(s1.begin() + i == s1.end())//最后一个单词找没有空格，所以找到s1.end()进行逆置{reverse(start, s1.end());}}cout << s1 << endl;}return 0;
}

 7.排序子序列

一定要注意，在一个非递增/非递减的区间里，是可以有重复的元素，但是在遍历整个数组的时候，遇到重复元素直接跳过！因为你放哪个区间都不合适，还会影响子序列的判断 

#include
#includeusing namespace std;int main(){int n;cin >> n;vector a;a.resize(n + 1);a[n] = 0;int i = 0;for (i = 0; i < n; ++i){cin >> a[i];}i = 0;int count = 0;while (i < n){// 非递减子序列if (a[i] < a[i + 1]){while (i < n && a[i] <= a[i + 1]){i++;}count++;i++;}else if (a[i] == a[i + 1]){i++;}else // 非递增子序列{while (i < n && a[i] >= a[i + 1]){i++;}count++;i++;}}cout << count << endl;return 0;}

8.数字三角形（蓝桥杯，学习一个大佬的博客....）

首先观察到这个题目要求

所以写一个dfs的代码，看一下最后的结果应该是什么样的 

#include 
#include 
#include 
using namespace std;int n;
vector< vector >flag(101);void dfs(int i, int j, int time)//向左，time-1;向右，time+1
{if (flag[i][j])//若当前点已递归过，则直接返回（降低时间复杂度）return;flag[i][j] = true;//当前点满足if (time == -1 && i + 1 < n)//必须向右dfs(i + 1, j + 1, 0);//向右下方点递归else if (time == 1 && i + 1 < n)//必须向左dfs(i + 1, j, 0);//向左下方点递归else if (!time && i + 1 < n)//可向左也可向右{dfs(i + 1, j + 1, 1);dfs(i + 1, j, -1);}else//其他情况则返回return;
}int main()
{cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < i + 1; j++)flag[i].push_back(false);//初始化为falsedfs(0, 0, 0);//从第一个点往下递归//输出结果for (int i = 0; i < n; i++){for (int j = 0; j < i + 1; j++)if (flag[i][j])cout << "1 ";elsecout << "0 ";cout << endl;}cout << endl << endl;return 0;
}

这个是n=11的代码

 n=10

发下规律，然后从倒数第二行往上动态规划

#include 
#include 
#include 
using namespace std;int n, tmp;
vector< vector >num(101);
vector< vector >flag(101);int main()
{// 请在此输入您的代码cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < i + 1; j++){cin >> tmp;num[i].push_back(tmp);flag[i].push_back(false);}if (n % 2)	//n为奇数，则最后一行有奇数个数，最中间的数可作为终点flag[n - 1][(n - 1) / 2] = true;else		//i为偶数，则最后一行有偶数个数，最中间两个数可作为终点{flag[n - 1][n / 2] = true;flag[n - 1][n / 2 - 1] = true;}for (int j = 0; j < n; j++)//最后一行其余的数设为0if (!flag[n - 1][j])num[n - 1][j] = 0;for (int i = n - 2; i >= 0; i--)//从倒数第二行往上遍历{for (int j = 0; j <= i; j++)//从左往右遍历{if (!flag[i + 1][j] && !flag[i + 1][j + 1])//该点不能到达num[i][j] = 0;//设为0，方便计算else										//该点能到达{num[i][j] += max(num[i + 1][j], num[i + 1][j + 1]);//取两者最大即可flag[i][j] = true;//标记该点能到达}}}cout << num[0][0] << endl;//输出结果return 0;
}

 9.跳跃（蓝桥杯）

#include 
#include 
#include "string.h"
#include 
#include 
using namespace std;int n, m;
vector< vector >weight(101);//每个点的权值
vector< vector >totoal_weight(101);//存储走到每个点的最大权值和long long find_max(int x, int y)//找到走到该点的所需的最大权值和（不包括该点的权值）
{long long max = LLONG_MIN;for (int i = x; i >= 1; i--)//从该点往上{for (int j = y; j >= 1; j--)//从该点往左{//1.不能原地踏步，所以不能与该点坐标一样//2.步数要小于等于3//3.要比当前的max大才更新maxif (!(x == i && y == j) && (x - i + y - j) <= 3 && max < totoal_weight[i][j])max = totoal_weight[i][j];}}if (max == LLONG_MIN)//说明是起点，返回0即可return 0;else                 //返回走到该点所需的最大权值和（不包括该点的权值）return max;
}int main()
{cin >> n >> m;int w;//临时变量，某点的权值for (int i = 1; i <= n; i++)    //行输入{weight[i].push_back(0);    //占位，因为j要从1开始，而数组下标从0开始totoal_weight[i].push_back(0);  //占位for (int j = 1; j <= m; j++)    //列输入{cin >> w;weight[i].push_back(w);         totoal_weight[i].push_back(w);}}for (int i = 1; i <= n; i++)        //从上往下{    for (int j = 1; j <= m; j++)    //从左往右{totoal_weight[i][j] += find_max(i, j);//得到每个点的最大权值和}}cout << totoal_weight[n][m] << endl;    //输出最后一个点的最大权值和return 0;
}

10.蓝肽子序列

#include 
#include 
using namespace std;
int dp[1005][1005];
string s1, s2;
string str1[1005], str2[1005];
int cnt1, cnt2;
int main()
{cin >> s1 >> s2;int d1 = s1.length(), d2 = s2.length();for (int i = 0; i < d1;){cnt1++;if (s1[i] >= 'A' && s1[i] <= 'Z'){str1[cnt1] += s1[i++];while (s1[i] >= 'a' && s1[i] <= 'z'){str1[cnt1] += s1[i++];}}}for (int i = 0; i < d2;){cnt2++;if (s2[i] >= 'A' && s2[i] <= 'Z'){str2[cnt2] += s2[i++];while (s2[i] >= 'a' && s2[i] <= 'z'){str2[cnt2] += s2[i++];}}}for (int i = 1; i <= cnt1; i++)for (int j = 1; j <= cnt2; j++){if (str1[i] == str2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}cout << dp[cnt1 ][cnt2 ] << endl;return 0;
}