CF 1072 D
题意 给你一个n*n的矩阵然后给你k代表能替换k次 然后从 (1,1)走向(n,n)
蒟蒻不会 一旁的zls看了一眼觉得我们要dp 但是dp不能记录答案路径 于是我们觉得预处理dp 处理出来前面能全替换成a的点 也就是坐标 i+j-1-k ==dp[i][j] 也就是说这条路径a的数目加上k等于路径的字符串长度 我们从能走的坐标标记出来 然后进行bfs bfs是zls的层层bfs 也就是你bfs一层记录最小的ch 然后找最小的ch去bfs 记录答案 注意如果k+dp[i][j]>=n+n-1代表路上都可以换成a 那么你就输出2n - 1 个a 但是k = 0 要特判 直接1 1bfs
#include <cstdio> #include <cmath> #include <queue> #include <stack> #include <iostream> #include <cstring> #include <algorithm> #include <map> #include <set> #include <vector> using namespace std; const int MAX_N = 2024; char str[MAX_N][MAX_N]; char ans[MAX_N]; int dp[MAX_N][MAX_N],vis[MAX_N][MAX_N]; int n,tot; int dir[2][2] = {1,0,0,1}; set<string > st; vector<pair<int ,int > > vt; queue<pair<int,int> >q; void bfs(){ while(!q.empty()){ int tim=q.size(); char ch='z'; while(tim--){ int xx,yy; xx=q.front().first,yy=q.front().second; q.pop(); if(xx==n&&yy==n){ for(int i=1;i<=tot;i++){ printf("%c",ans[i]); } puts(""); return ; } if(xx+1<=n&&!vis[xx+1][yy]){ vis[xx+1][yy]=1; q.push(make_pair(xx+1,yy)); if(str[xx+1][yy]<ch){ ch=str[xx+1][yy]; } } if(yy+1<=n&&!vis[xx][yy+1]){ vis[xx][yy+1]=1; q.push(make_pair(xx,yy+1)); if(str[xx][yy+1]<ch){ ch=str[xx][yy+1]; } } } ans[++tot]=ch; tim=q.size(); while(tim--){ int xx,yy; xx=q.front().first; yy=q.front().second; q.pop(); if(str[xx][yy]==ch){ q.push(make_pair(xx,yy)); } } } } int main() { int k; scanf("%d%d",&n,&k); int ans_ij=0; for(int i = 1; i<=n; ++i){ getchar(); for(int j = 1;j<=n;++j){ scanf("%c",&str[i][j]); //printf("%c",str[i][j]); } //printf("\n"); } dp[1][1]=(str[1][1]=='a'?1:0); for(int i = 1; i<=n; ++i) for(int j = 1; j<=n; ++j) { dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + (str[i][j]=='a'?1:0); } int ans_tmp=0; for(int i = 1; i<=n; ++i) for(int j = 1; j<=n; ++j) { if(i+j-k==dp[i][j]+1) { if(i+j>=ans_ij) { if(i+j==ans_ij) { ans_ij = i+j; vt.push_back(make_pair(i,j)); } else { ans_tmp = dp[i][j]; ans_ij = i + j; vt.clear(); vt.push_back(make_pair(i,j)); } } } } if(dp[n][n]+k>=n+n-1){ for(int i=1;i<=2*n-1;i++) printf("a"); puts(""); return 0; } if(k==0){ tot=1; ans[1]=str[1][1]; q.push(make_pair(1,1)); } else{ tot=ans_ij-1; for(int i=1;i<=tot;i++){ ans[i]='a'; } int sz = vt.size(); for(int i = 0; i<sz; ++i) { vis[vt[i].first][vt[i].second] = 1; q.push(make_pair(vt[i].first,vt[i].second)); } } bfs(); //cout <<ans_ij << endl; return 0; }
