笔试专题（十四）

mari和shiny

题目链接

题解

1. 可以用多状态的线性dp
2. 细节处理：使用long long 存储个数
3. 空间优化：只需要考虑等于’s’，‘sh’，'shy’的情况，因为等于的情况，前面会保存起来，不需要统计

代码

#include<iostream>
#include<string>using namespace std;int main()
{int n;string str;cin >> n >> str;long long s = 0,sh = 0,shy = 0;for(int i = 0;i < n;i++){char ch = str[i];if(ch == 's') s++;else if(ch == 'h') sh += s;else if(ch == 'y') shy += sh;}cout << shy << '\n';return 0;
}

体操队形

题目链接

题解

1. dfs
2. 画出一颗决策树比什么都重要，一定要画图，然后仔细想，返回条件，剪枝，pos位置，每个位置枚举几个点啊，题目要求的剪枝等等

代码

#include<iostream>using namespace std;int n;
int a[15];
int ans;
bool vis[15];// 标记用过的数字void dfs(int pos)
{if(pos == n + 1){ans++;return;}for(int i = 1;i <= n;i++){// 剪枝// 如果不满足i排在a[i]的前面的话// if(vis[i]) continue;// 表示i这个点已经用过了,// 这个位置要枚举下一个点，看是否也用过了,剪枝// if(vis[a[i]]) return;// 2号这个点要放在1号前面,// 但是1号已经用过了,后面所有数都是错的了，所以剪枝if(vis[i] == false){// if(vis[a[i]]) return;// 为什么这句不能放在vis[i] = false的外面// 单独这句确实不行，因为i每次从1开始，会导致错误// 但下一次递归需要剪枝用过的点if(vis[a[i]]) return;// 未用过的点才会进来vis[i] = true;dfs(pos+1);// 为什么不能用i+1// o,因为每次进来都是i+1位置,// i都是1,i+1= 2每次都是二号位置vis[i] = false;}}return;
}
int main()
{cin >> n;for(int i = 1;i <= n;i++) cin >> a[i];dfs(1);cout << ans << '\n';return 0;
}

二叉树中的最大路径和

题目链接

题解

1. dfs，树形dp
2. 可以分解为子问题，求每条路径的最大单链和，为什么是单链和呢？因为不能走回头路，一个节点只能包含一次，那么可以求左子树的最大单链和，右子树的最大单链和
3. 返回值是以我为根节点的最大单链和，要么是我自己，要么是我自己加上右子树，要么是我自己加上左子树
4. 每次都需要更新最大的单链和，我自己加上左右子树，因为不一定经过根节点

代码

class Solution 
{
public:int ret = INT_MIN;int maxPathSum(TreeNode* root) {dfs(root);return ret;}// 要返回左右子树的最大单链和int dfs(TreeNode* root){if(root == nullptr) return 0;int left = max(dfs(root->left),0);int right = max(dfs(root->right),0);int k = root->val + left + right;ret = max(ret,k);return root->val + max(left,right);}
};