今天周赛难度比上次（259场）难点儿。第一题常规签到，数据规模不大，做题的时候直接暴力过的，刚刚复盘重新写了个o(n)的代码；第二题前缀和，要注意思考什么情况下才是真正的"最大、最小"；第三题直接模拟；第四题区间dp，注意利用好 "表达式结果最大值不会超过1000" 这个条件。
keywords：前缀和；模拟；区间dp
5881. 增量元素之间的最大差值
【题目描述】
【思路】
最大规模只有1000，两重循环查找可以过。也可以每次维护一个最小值，用当前值减去最小值来获取最大差，这样复杂度可降到o(n)。
【代码】
class Solution {public:int maximumDifference(vector<int>& nums) {int minn=nums[0],ans=0;for(int i=1;i<nums.size();i++){minn=min(minn,nums[i]);ans=max(nums[i]-minn,ans);}return ans==0?-1:ans;}};
5882. 网格游戏
【题目描述】
【思路】
第一个人的目的就是让第二个人的得分最小，第二个人则在第一个人清理过的网格中尽量多地捡分，这是一类题。之前没总结过，姑且在这记录一个不太成熟的总结。这类题首先要理解清楚二者的目的，然后关注第一个人清理过后，在这基础上第二个人有哪些选择。第一个人目的是要让第二个人可能的得分最小化，他宁可自己收获少些也要让第二个人得到的尽量少。
两个人均只能向右或者向下走，又由于网格只有两行，任何人往下走了一次后（出发点是左上角）就只能往右走了，只能拐一次弯，所以有下面这个图：
第一个人走过的地方分数会被清零，还有分数的位置剩下两块，图中蓝色和绿色部分。第二个人以尽量多拿分的原则走，可以拿到蓝色或者绿色部分所有的分，但不能兼得（因为只能向右或向下走，前面已说明），所以每次第一个人处理过后，第二个人可获得的最大分数就是蓝色或者绿色部分的和。这里序列和显然前缀和是不错的选择。第一个人的拐点可以 0 - n-1任意一列处，所以枚举每一个位置，找到第二人可获得的最大分数的最小值即可，复杂度o(n)。
【代码】
const int N=100010;class Solution {public:long long int sum[2][N];long long gridGame(vector<vector<int>>& grid) {memset(sum,0,sizeof sum);int n=grid[0].size();for(int i=1;i<=n;i++){sum[0][i]=grid[0][i-1]+sum[0][i-1];sum[1][i]=grid[1][i-1]+sum[1][i-1];}int id=-1;long long maxn=1e10;for(int i=1;i<=n;i++)maxn=min(maxn,max(sum[1][i-1],sum[0][n]-sum[0][i]));return maxn;}};
5883. 判断单词是否能放入填字游戏内
【题目描述】
【代码】
class Solution {public:bool placeWordInCrossword(vector<vector<char>>& board, string word) {int m = board.size(), n = board[0].size(), len = word.size();string rword=word;reverse(rword.begin(),rword.end());for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]=='#')continue;int k=j;bool f1=true,f2=true;for(j ; j<n && board[i][j]!='#' ; j++){if(j-k >= len || (board[i][j]!=' ' && word[j-k]!=board[i][j]))f1=false;if(j-k >= len || (board[i][j]!=' ' && rword[j-k]!=board[i][j]))f2=false;}if((f1==true || f2==true) && j-k == len) return true;}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[j][i]=='#')continue;int k=j;bool f1=true,f2=true;for(j ; j<m && board[j][i]!='#'; j++){if(j-k >= len || (board[j][i]!=' ' && word[j-k]!=board[j][i]))f1=false;if(j-k >= len || (board[j][i]!=' ' && rword[j-k]!=board[j][i]))f2=false;}if((f1==true || f2==true) && j-k == len) return true;}}return false;}};
5884. 解出数学表达式的学生分数
【题目描述】
【思路】
首先，表达式求值借助一个栈很容易求出来。剩下的难点就在于如何找出计算顺序错误时的计算结果。对于一个串 xOy，O表示一个运算符，此处可以是'+' 或 '*'，x，y可以是一个串也可以是一个数字。xOy串所有可能的运算结果可以由x和y串中所有可能结果通过O（乘或加）运算得到，这里动态规划的思路就显而易见了。具体对应哪种动态规划，可以一个个套。
用dp[i][j]记录s[i...j]这个子串的所有运算结果，状态转移前面已经描述了：
const int N=1010;class Solution {public:int count[N];int Right_ans(string s){stack<int> stk;stk.push(s[0]-'0');for(int i=1;i<s.length();i+=2){if(s[i]=='+')stk.push(s[i+1]-'0');else{stk.top() *= (s[i+1]-'0');}}int sum=0;while(!stk.empty()){sum += stk.top();stk.pop();}return sum;}int scoreOfStudents(string s, vector<int>& answers) {memset(count,0,sizeof count);for(auto &x:answers)count[x]++;int right_ans=Right_ans(s);int n=s.length();unordered_set<int> dp[40][40];for(int j=0;j<n;j++)dp[j][j].insert(s[j]-'0');for(int len=2; len<n; len+=2){for(int i=0; i+len < n; i+=2){int j=i+len;for(int t=0; t < len; t+=2){for(auto &x : dp[i][i+t]){for(auto &y : dp[i+t+2][j]){if(s[i+t+1]=='+'){if( x+y <= 1000)dp[i][j].insert( x+y );}else{if( x*y <= 1000)dp[i][j].insert( x*y );}}}}}}int scores=5*count[right_ans];for(auto &x : dp[0][n-1]){if(x!=right_ans) scores += 2*count[x];}return scores;}};
