2024.5.29晚训参考代码

因为本套题没有BFS例题，所以我先把BFS模板放着

#includeusing namespace std;int n,m;//n*m的棋盘 int dis[402][402]; bool vis[402][402];int X[]={-2,-2,-1,-1,1,1,2,2};//偏移量的表 int Y[]={-1,1,-2,2,-2,2,-1,1};//定义一个数组，我直接把这些元素从0位置填充进去 struct node{int x;int y;int dis;//从起点走到当前(x,y)的最短步数 };int st,ed;//起点x  y坐标 void bfs(){  queueq;node now;now.x=st;now.y=ed;now.dis=0;q.push(now);//放入队列，第一个搜索的状态 dfs(st,ed,0)  while(!q.empty()){//第一步取出队首状态//第二步，弹出队首 //第三步  判断当前状态是不是已经走过了   后面再来到这个点肯定不是最短距离//仅限于所有距离都一样的情况   //第四步   判断当前的点是不是终点 //第五步  打标记//第六步  做相关的数据统计  比如记录(now.x,now.y)的最小步数  //第七步  以这个点拓展出去的其余状态  注意判断非法情况   }//bfs结束 }signed main(){int x,y;cin>>n>>m;cin>>st>>ed;//memset(dis,-1,sizeof(dis));//初始化数组    for(int i=1;ifor(int j=1;jdis[i][j]=1e9;//表示不可到达  }}//dis[i][j]表示从起点走到(i,j)的最短距离 bfs();for(int i=1;ifor(int j=1;j//dis[i][j]=1e9;//表示不可到达  if(dis[i][j]==1000000000)coutint x;int y;int dis;//从起点走到(x,y)的距离 }; int n,m,x,y;int X[]={-1,-1,-2,-2,1,1,2,2};int Y[]={2,-2,-1,1,2,-2,1,-1};int dis[405][405];int vis[405][405];void bfs(){queuenode now=q.front();q.pop();if(vis[now.x][now.y]==1){continue;//已经走过这个点了  }dis[now.x][now.y]=now.dis;vis[now.x][now.y]=1;node cnt;for(int i=0;icnt.x=now.x+X[i];cnt.y=now.y+Y[i];cnt.dis=now.dis+1;if(cnt.xcinnmxy;for(int i=1;ifor(int j=1;jdis[i][j]=-1;}}bfs();for(int i=1;ifor(int j=1;jcoutif(xcinnmsb;coutint n,m;cinnm;cinA+1B+1;for(int i=1;ifor(int j=1;jif(A[i]==B[j]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1]));}}}coutint n;cinn;//dp[0][0]=dp[0][]//dp[i][0] 没抢i银行  for(int i=1;ilong long x;cinx;//cout    //总背包容量10   //只考虑拿价值高的    价值是10，体积是10     可能有其他财宝价值5  体积1  有若干个    //dfs(拿/不拿)  暴力   n cinV[i]W[i];//输入体积  和  价值   }for(int i=1;ifor(int j=M;j=V[i];j--){dp[j]=max(dp[j],dp[j-V[i]]+W[i]);}}coutcinTM;for(int i=1;i    /* 考虑区间dp  dp[l][r]= 表示把[L,R]的石头合并成一堆所需要的最小花费     考虑转移 1 1 1 1 1 1 1 所有大的区间一定由小区间转移  考虑合并成长度为2的区间// dp[i][i+1]=(dp[i][i]+dp[i+1][i+1])+w[i]+w[i+1]  合并成3区间  来自于长度为2 + 拼长度为1   长度为4的区间  1+3  2+2  3+1  ....  考虑dp[l][r] 拆成两个区间，进行合并  */ int n; cinn; for(int i=1;i cinw[i]; sum[i]=sum[i-1]+w[i];//前缀和  }  for(int len=1;len for(int i=1;i     //i作为区间起点 //枚举区间长度//计算右端点在哪int j=i+len;dp[i][j]=1e9;if(jn)break;  for(int k=i;k dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); } } }   coutcin  n;for(int i = 1; i cin  m[i];m[i + n] = m[i];}memset(dp1,0x3f3f3f3f,sizeof(dp1));memset(dp2,-1,sizeof(dp2));for(int i = 1; i s[i] = s[i - 1] + m[i];dp1[i][i] = 0;dp2[i][i] = 0;}for(int i = 2; i for(int l = 1; l int r = l + i - 1;for(int j = l; j