2.4学习总结

2.4
1.不相交的线
2.最⼤⼦序和
3.判断⼦序列
4.不同的子序列
5.编辑距离
6.零的数列 Zero Sum
7.迷宫与陷阱

https://leetcode.cn/problems/uncrossed-lines/description/

还是找最长公共子序列的问题

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int dp[505][505];
        memset(dp,0,sizeof(dp));
        for (int i=1;i<=nums1.size();++i){
            for (int j=1;j<=nums2.size();++j){
                if (nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};

https://leetcode.cn/problems/maximum-subarray/description/

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int>dp(nums.size()+1,0);
        dp[0]=nums[0];
        int res=dp[0];
        for (int i=1;i<nums.size();++i){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            if (dp[i]>res)res=dp[i];
        }
        return res;
    }
};

https://leetcode.cn/problems/is-subsequence/description/

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
        for (int i=1;i<=s.size();++i){
            for (int j=1;j<=t.size();++j){
                if (s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        int res=dp[s.size()][t.size()];
        if (res==s.size())return true;
        else return false;
    }
};

https://leetcode.cn/problems/distinct-subsequences/description/

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
        for (int i=0;i<=s.size();++i) dp[i][0]=1;
        for (int i=1;i<=s.size();++i){
            for (int j=1;j<=t.size();++j){
                if (s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                else dp[i][j]=dp[i-1][j];
            }
        }
        return dp[s.size()][t.size()];
    }
};

https://leetcode.cn/problems/edit-distance/description/

编辑距离是经典的动态规划问题，当遇到两个字符相等的时候，就直接保持上一个状态，如果不相等，就删除第一个字符串的字符，或者删除第二个字符串的字符，或者替换一个字符，所以就可以得到转移方程，

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for (int i=0;i<=word1.size();++i) dp[i][0]=i;
        for (int j=0;j<=word2.size();++j) dp[0][j]=j;
        for (int i=1;i<=word1.size();++i){
            for (int j=1;j<=word2.size();++j){
                if (word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

零的数列 Zero Sumhttps://www.luogu.com.cn/problem/P1473

题目描述

请考虑一个由 11 到 �N 的数字组成的递增数列：1,2,3,…,�1,2,3,…,N。

现在请在数列中插入 + 表示加，或者 - 表示减， （空格） 表示空白（例如 1-2 3 就等于 1-23），来将每一对数字组合在一起（请不要在第一个数字前插入符号）。

计算该表达式的结果并判断其值是否为 00。 请你写一个程序找出所有产生和为零的长度为N的数列。

输入格式

单独的一行表示整数 �N（3≤�≤93≤N≤9）。

输出格式

按照 ASCI I码的顺序，输出所有在每对数字间插入 +，-， （空格） 后能得到结果为零的数列。

输入输出样例

输入 #1复制

7

输出 #1复制

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

思路：用DFS直接暴力搜索，重难点在于检查函数的实现

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long 
char fuhao[3]={' ','+','-'};
int n;
int a[11];
bool check(){
	int res=0;
	for (int i=1;i<=n;++i){
		if (a[i]==0) continue;
		int t=i;
		for (int j=i+1;j<=n;++j){
			if (a[j]!=0)break;
			t=t*10+j;
		}
		if (a[i]==1) res+=t;
		else res-=t;
	}
	if (res==0)return true;
	else return false;
}
void dfs(int x){
	if (x==n+1){
		if (check()){
			cout<<1;
			for (int i=2;i<=n;++i){
				cout<<fuhao[a[i]]<<i;
			}
			cout<<endl;
			return ;
		}else return ;
	}
	for (int i=0;i<=2;++i){
		a[x]=i;
		dfs(x+1);
		a[x]=0;
	}
}
signed main(){
	cin>>n;
	a[1]=1;
	dfs(2);
}
	

迷宫与陷阱https://www.luogu.com.cn/problem/P8673

题目描述

小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 �×�N×N 个格子组成的二维迷宫。

小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。

每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。

迷宫中有些格子小明可以经过，我们用 . 表示；

有些格子是墙壁，小明不能经过，我们用 # 表示。

此外，有些格子上有陷阱，我们用 X 表示。除非小明处于无敌状态，否则不能经过。

有些格子上有无敌道具，我们用 % 表示。

当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 �K 步。

之后如果再次到达该格子不会获得无敌状态了。

处于无敌状态时，可以经过有陷阱的格子，但是不会拆除 / 毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。

给定迷宫，请你计算小明最少经过几步可以离开迷宫。

输入格式

第一行包含两个整数 �N 和 �K。(1≤�≤1000，1≤�≤10)(1≤N≤1000，1≤K≤10)。

以下 �N 行包含一个 �×�N×N 的矩阵。

矩阵保证左上角和右下角是 .。

输出格式

一个整数表示答案。如果小明不能离开迷宫，输出 −1−1。

输入输出样例

输入 #1复制

5 3
...XX
##%#.
...#.
.###.
.....

输出 #1复制

10

输入 #2复制

5 1
...XX
##%#.
...#.
.###.
.....

输出 #2复制

12

思路：套BFS的模版，加上一些状态判断

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long 
const int N=1005;
char a[N][N],vis[N][N];
int n,k;
int dir[4][2]={
  {0,1},{1,0},{0,-1},{-1,0}};
struct node{
	int x;
	int y;
	int s;
	int w;
};
queue<node>q;
signed main(){
	cin>>n>>k;
	memset(vis,-1,sizeof(vis));
	for (int i=0;i<n;++i){		
			cin>>a[i];
	}
	q.push({0,0,0,0});
	vis[0][0]=0;
	while (!q.empty()){
		node now=q.front(); q.pop();
		int x=now.x,y=now.y,s=now.s,m=now.w;
		if (x==n-1 && y==n-1){
			cout<<s;
			return 0;
		}
		for (int i=0;i<4;++i){
			int tx=x+dir[i][0],ty=y+dir[i][1];
			if (tx<0 || ty<0 || tx>=n || ty>=n)continue;
			if (a[tx][ty]=='X' && now.w==0){
				continue;
			}
			if (now.w-1>0)m=now.w-1;
			else m=0;
			if (a[tx][ty]=='%'){
				m=k;
			}
			if (vis[tx][ty]<m && a[tx][ty]!='#'){
				vis[tx][ty]=m;
				q.push({tx,ty,s+1,m});
			}
		}
	}
	cout<<-1;
	return 0;
}