编辑距离

这似乎是一个动态规划问题。涉及到了状态转移方程相关的问题。 d(i, j) = a(i, j) + max{d(i + 1, j), d(i + 1, j + 1)} 看了一下官方解析（学校给的），原来是上次电脑坏了没做的2857，具体流程是这样的的： s1长度为m s2长度为n 从i = 0， j = 0开始一直到m/n 这样考虑： 1.i = 0/j = 0，这时edit（0，j）= edit(0, j - 1) + 1如果j为0，同理 2.i > 0/ j > 0; i=j时edit（i ， j）= edit（i-1，j-1） i！=j时又分为三种情况 1）i换j，那就是i，j= i-1，j-1 + 1 2）I删除，i-1变j， 那就是i，j=i-1，j + 1 3）i后面添加j，i,j = i,j-1 + 1 取以上的最小值就好了

#include <iostream> #include <cmath> using namespace std; int min(int x, int y, int z) { int min = x > y ? y : x; min = min < z ? min : z; return min; } int main(int argc, const char * argv[]) { int T; cin >> T; for(int i = 0; i < T; i++) { string s1, s2; int dp[501][501]; dp[0][0] = 0; cin >> s1 >> s2; for(int i = 0; i < s1.size(); i++) dp[i + 1][0] = dp[i][0] + 1; for(int j = 0; j < s2.size(); j++) dp[0][j + 1] = dp[j][0] + 1; for(int i = 1; i <= s1.size(); i++) { for(int j = 1; j <= s2.size(); j++) { dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1)); } } cout << dp[s1.size()][s2.size()] << endl; } return 0; }

最短路径问题：

这道题的算法……emmm我又学到了 一个图里面经常用到的算法。（忘记名字了）

#include <iostream> #include <cmath> #include <algorithm> using namespace std; int main(int argc, const char * argv[]) { int n, m, dis[601][601], len[601]; cin >> n >> m; for(int i = 0; i < 601; i++) for(int j = 0; j < 601; j++) dis[i][j] = 1e7; for(int i = 0; i < 601; i++) len[i] = 1e7; bool flag[600] = {false}; for(int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; dis[u - 1][v - 1] = w; } for(int i = 0; i < n; i++) len[i] = dis[0][i]; flag[0] = 1; len[0] = 0; for(int i = 0; i < n; i++) { int k = 600; for(int j = 0; j < n; j++) if(!flag[j] && len[j] < len[k]) k = j; flag[k] = 1; for(int j = 0; j < n; j++) if(!flag[j] && len[k] + dis[k][j] < len[j]) len[j] = len[k] + dis[k][j]; } if(len[n - 1] > 1e6) cout << -1; else cout << len[n - 1]; return 0; }

逃课吃鸡

看了大佬的算法教会了我用map+vector，字符串和时间一对一，直接vector排序就可以了。省时省空间，岂不美哉。 顺便：for（auto &it ：p） 等价于 for（it = p.begin（）；it ！= p.end（）；it++）

数据结构关于graph

那道题错的点在于用链式list存储了一个点链接的其他点，这个不太可靠，因为访问需要从小到大但是给的数据让你储存不一定是从小到大的。所以我们需要采取list.sort（）函数直接对它进行从小到大的排序