RC-u2 女王的大敕令
当时我写的时候还dfs()去枚举开始点和停留点
其实完全没有必要，直接4层for循环
2层枚举开始点，其余两层枚举停留点
然后判断开始点与停留点之间的步数是否合法
是否会被怪物击中即可
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; int mr[5],v[5],fy,fx,d1,d2; struct node{ int y1,x1,y2,x2; }; vector<node>ans; bool judge(int y1,int x1,int y2,int x2) { if (abs(y1-y2)+abs(x1-x2)!=d1 || abs(fy-y2)+abs(fx-x2)!=d2) return false; if (y1==mr[4]+v[4] || y1==mr[3]-v[3]|| x1==mr[2] || x1==mr[1]) return false; if (y2==mr[4]+v[4] || y2==mr[3]-v[3]|| x2==mr[2]-v[2] || x2==mr[1]+v[1]) return false; return true; } int main() { for (int i=1;i<=4;i++) cin>>mr[i]; for (int i=1;i<=4;i++) cin>>v[i]; cin>>fy>>fx>>d1>>d2; for (int y1=1;y1<=5;y1++) for (int x1=1;x1<=5;x1++) for (int y2=1;y2<=5;y2++) for (int x2=1;x2<=5;x2++) { if (!judge(y1,x1,y2,x2)) continue; ans.push_back({y1,x1,y2,x2}); } for (int i=0;i<ans.size();i++) { node t=ans[i]; cout<<t.y1<<" "<<t.x1<<" "<<t.y2<<" "<<t.x2<<endl; } return 0; }
RC-u3 战利品分配
上面种种迹象表明这道题可以用bfs写，但是注意！
bfs中我们有st[]数组，判断是否重复走点了
因为我们是要重复到终点城市的，
所以注意终点城市的st不要设置为true,或者要特判
#include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N=1e5+5; int n,m,k,p,w[N],st,fin; vector<int>sides[N]; bool vis[N]; struct node{ int id,sp,v; }; int ans=0,msp=0x3f3f3f3f; void bfs() { queue<node>q; if (p==1) q.push({st,1,w[st]}); else q.push({st,1,0}); vis[st]=true; while (q.size()) { node f=q.front();q.pop(); if (f.id==fin) { if (f.sp>msp) break; else { msp=f.sp,ans=max(ans,f.v); continue; } } for (int i=0;i<sides[f.id].size();i++) { int ch=sides[f.id][i]; if (vis[ch] && ch!=fin) continue; vis[ch]=true; int v=f.v; int sp=f.sp+1; if (p==k && sp%k==0) v+=w[ch]; else if (sp%k==p) v+=w[ch]; q.push({ch,sp,v}); } } } int main() { cin>>n>>m>>k>>p; for (int i=1;i<=n;i++) cin>>w[i]; for (int i=1;i<=m;i++) { int a,b; cin>>a>>b; sides[a].push_back(b),sides[b].push_back(a); } cin>>st>>fin; bfs(); cout<<ans<<endl; return 0; }
RC-u4 变牛的最快方法
最短编辑距离问题<----
关于这一类模型我先亮出我的疑惑：
假设数组 A 与 数组 B，数组A要匹配数组B
只能通过：不变，改变，增，删 操作
问最小操作次数
为何 当A[i]==B[i]时 选择不变时最优的呢？能不能通过其他操作使得整体更优？
有两种dfs方式：
1.dfs(0,0)开始,
dfs(i,j)含义为数组A ,i~A.size 与 数组B j~B.size 匹配上的最小操作次数
2.dfs（a.size()-1,b.size()-1）开始
dfs(i,j)含义为数组A 0~i 与 数组 B 0~j 匹配上的最小操作次数
为何一般情况下1比2方法慢很多？
其余就是博客是有的了，代码如下，for循环dp不知道为何错了，就不放出：
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 1005; vector<int> a, b; struct node { int i, j, op, t; }; node path[N][N]; int dp[N][N]; int dfs(int i, int j) { if (dp[i][j] != -1) return dp[i][j]; if (i >= a.size()) { path[i][j] = {-1, -1, 3, int(b.size() - j)}; return b.size() - j; } if (j >= b.size()) { path[i][j] = {-1, -1, 0, int(a.size() - i)}; return a.size() - i; } if (a[i] == b[j]) { dp[i][j] = dfs(i + 1, j + 1); path[i][j] = {i + 1, j + 1, 2, 1}; return dp[i][j]; } else { int ans1 = dfs(i + 1, j + 1) + 1; int ans2 = dfs(i, j + 1) + 1; int ans3 = dfs(i + 1, j) + 1; dp[i][j] = min(ans1, min(ans2, ans3)); if (dp[i][j] == ans1) path[i][j] = {i + 1, j + 1, 1, 1}; else if (dp[i][j] == ans2) path[i][j] = {i, j + 1, 3, 1}; else if (dp[i][j] == ans3) path[i][j] = {i + 1, j, 0, 1}; return dp[i][j]; } } int main() { int t, i, j; while (cin >> t && t != -1) a.push_back(t); while (cin >> t && t != -1) b.push_back(t); memset(dp, -1, sizeof(dp)); cout << dfs(0, 0) << endl; i = 0, j = 0; while (i != -1 && j != -1) { int op = path[i][j].op, t = path[i][j].t; for (int k = 1; k <= t; k++) cout << op; int l = path[i][j].i, r = path[i][j].j; i = l, j = r; } return 0; }
#include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<stack> using namespace std; const int N=1005; struct node{ int i,j,op,t; }; node path[N][N]; vector<int>a,b; int dp[N][N]; int dfs(int i,int j) { if (dp[i][j]!=-1) return dp[i][j]; if (i<=0) { path[i][j]={-1,-1,3,j}; return j; } if (j<=0) { path[i][j]={-1,-1,0,i}; return i; } if (a[i]==b[j]) { dp[i][j]=dfs(i-1,j-1); path[i][j]={i-1,j-1,2,1}; return dp[i][j]; } else { int ans1=dfs(i-1,j-1)+1; int ans2=dfs(i,j-1)+1; int ans3=dfs(i-1,j)+1; dp[i][j]=min(ans1,min(ans2,ans3)); if (dp[i][j]==ans1) path[i][j]={i-1,j-1,1,1}; else if (dp[i][j]==ans2) path[i][j]={i,j-1,3,1}; else if (dp[i][j]==ans3) path[i][j]={i-1,j,0,1}; return dp[i][j]; } } int main() { int t,i,j; a.push_back(-1),b.push_back(-1); while (cin>>t && t!=-1) a.push_back(t); while (cin>>t && t!=-1) b.push_back(t); memset(dp,-1,sizeof(dp)); cout<<dfs(a.size()-1,b.size()-1)<<endl; i=a.size()-1,j=b.size()-1; stack<int>sk; while (i!=-1 && j!=-1) { int op=path[i][j].op,t=path[i][j].t; for (int k=1;k<=t;k++) sk.push(op); int l=path[i][j].i,r=path[i][j].j; i=l,j=r; } while (sk.size()) { cout<<sk.top(); sk.pop(); } return 0; }