笔试回顾1 | 翻大车

简单记一下自己没出的两道题吧

1.字符串最大得分

题目描述：

给一个字符串，里面都是小写字母，如果一个字母可以被标记（标记条件为隔壁字母和它相邻，相邻的意思就是b和a是相邻的，b和c是相邻的），那么就可以标记它和它隔壁的字母，获取它和隔壁的分数（a为1分，b为2分，以此类推），一个字母只能被标记一次。求最高分数。

输入：abb

输出：4

没做出来的原因：

贪心思想先入为主，想在当下就确定s[i]要跟前面的组还是跟后面的组，总结来说，脑子瓦特了没想到DP（其实想到了但自己把自己否了）。

代码块与解题思路：

#include<bits/stdc++.h>
using namespace std;
int main(){
// 最最最原式的线性DP，跟抛硬币例题没什么差别
// dp[i]表示前i个字符(包含i)中能获得的最大比分,每次选择是否加入s[i]
	string s;cin>>s;
	int n = s.size();
	vector<int> dp(n+10,0);//dp[i+1]表示s[i]前（算上s[i]）能获得的最大分数
	for(int i=1;i<n;i++){//从第二个字符开始
        if(abs(s[i]-s[i-1])<=1){
        //要么不加s[i]这个字符,要么加,加的话一定是一次加两个的
			dp[i+1]=max(dp[i],dp[i-1]+s[i]-'a'+1+s[i-1]-'a'+1);
		}
        else	dp[i+1]=dp[i]
	}
	cout<<dp[n]<<endl;
	return 0;
}

2.小红闯沼泽地

题目描述：

在沼泽地中移动，1代表沼泽，0代表平地。

在相同的地方里移动消耗1，否则消耗2。

求从0，0处到n-1,m-1处最少消耗多少。

输入：3 3

1 0 0

1 1 1

0 0 1

输出：4

没做出来的原因：

1.自己并没有完全理解记忆化dfs。

先前的理解：

该结点走过了所有能通往的地方后就为dp数组赋值，那么下次来的时候就不用继续搜了，直接获取dp数组的值就好了。

这种理解表面上好像可行，但它无法应对有可能往回走的场景，比如现在需求是从(1,1)走到(3,3)的最短路，可以左右下走；当前处于(2,1)，是由(2,2)来的，那么在尝试走过(3,1)后就会为dp数组赋值了，但其实存在从(1,1)->(2,1)->(2,2)的走法，而dp数组赋值后就否定了这种走法。

理论点讲，每次到这个点的状态不同会影响着我能不能往左走，也就是说少记了一个状态。

这种思路只有在只能往右往下走的时候是有效的，而我对记忆化dfs片面的理解一直让我以为自己掌握了，这是翻车的主要原因。

正确的理解：

这道题用记忆化dfs和二维DP都不能应对向左走的情况，不过记忆化dfs能做到一种小剪枝，即dp数组记下起点到该点的距离，下次走到这的时候判断过来的路是否更短，只有更短才会继续往下走，这样就免去没必要走的一段路。

这道题的正确解法应该是Dijkstra最短路。

2.对自己的莫名自信 + 思维的不灵活

第二题没写就跑去写最后一题，第二题真的是最最最基础的DP了，跟抛257硬币凑27一样基础，自己没看出来属实是思维大寄了；还有就是自己一直坚信记忆化DFS的解法是没错的，怀疑没出正确结果是因为自己某个小地方写错了而已，其实就算自己没写Dijkstra,去掉向左的情况去跑也能拿90%的分。

代码块：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;cin>>n>>m;
    vector<vector<int>> mad(n+10,vector<int>(m+10,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mad[i][j];//1代表沼泽,0代表平地
        }
    }
    vector<vector<int>> dire={{0,1},{1,0}};
    vector<vector<int>> visit(n+10,vector<int>(m+10,0));
    vector<vector<int>> dp(n+10,vector<int>(m+10,INT_MAX));//dp[i][j]表示从i,j位置到终点所花费的最小时间
    function<int(int,int)> dfs = [&](int i,int j){//坐标,记忆化搜索,返回值是从这个点到终点的距离
        if(i==n && j==n){
            return 0;
        }
        if(dp[i][j]!=INT_MAX)	return dp[i][j];
        int ans=INT_MAX/2;
        for(int k=0;k<2;k++){//往三个方向走
            int nexti=i+dire[k][0],nextj=j+dire[k][1];
            //dp[i][j]=INT_MAX表示这个点没走过或者无法走到终点,dp[i][j]!=INT_MAX表示已经走过了
            if(nexti>n || nextj>m || nexti<=0 || nextj<=0 || visit[nexti][nextj])    continue;//越界或走过了直接不走
            //沼泽进沼泽花费1时间,1*1
            //沼泽进入平地或平地进入沼泽花费2时间,1*0或0*1
            visit[nexti][nextj]=1;
            if(mad[nexti][nextj]*mad[i][j])    ans=min(ans,1+dfs(nexti,nextj));
            else    ans=min(ans,2+dfs(nexti,nextj));
            cout<<i<<" "<<j<<" "<<ans<<endl;
            visit[nexti][nextj]=0;
        }
        dp[i][j]=ans;
        return ans;
    };
    visit[1][1]=1;
    cout<<dfs(1,1)<<endl;
    return 0;
}

挺可惜的，解题决策不对，记忆化dfs的片面理解，吃一堑长一智吧。