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);}
};