題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè) $n?m$ 的矩陣，每個(gè)點(diǎn)都可以到達(dá)相鄰的四個(gè)點(diǎn)，每條邊都有一個(gè)邊權(quán)，問對于每個(gè)點(diǎn) $(i,j)$，走 $k$ 步可以回到 $(i,j)$ 的最短路徑

題目分析：首先不難看出 $k$ 如果是奇數(shù)的話無解，然后可以將題目轉(zhuǎn)換為：從 $(i,j)$ 走 $\frac{k}{2}$ 步可以到達(dá)的最短路徑，不難看出用后 $\frac{k}{2}$ 步沿著前面的路徑原路返回這樣一定是最優(yōu)的

第一反應(yīng)是暴力每個(gè)點(diǎn)，就是對于每個(gè)點(diǎn) $(x,y)$ 來說單獨(dú)思考，$d{p}_{i,j,k}$ 代表從點(diǎn) $(x,y)$ 出發(fā)走了 $k$ 步到達(dá)點(diǎn) $(i,j)$ 的最短路徑，這樣思考正確性毋庸置疑，就是時(shí)間復(fù)雜度有點(diǎn)大：$O(n?m?\frac{k}{2}?\frac{k}{2}?\frac{k}{2}?4)$，三個(gè) $\frac{k}{2}$ 分別代表需要轉(zhuǎn)移的矩形的長和寬，以及需要迭代的次數(shù)，$4$ 代表的是每次需要向四個(gè)方向轉(zhuǎn)移

后來發(fā)現(xiàn)，我們并不需要關(guān)注起點(diǎn)在哪，只需要關(guān)注走了 $\frac{k}{2}$ 步之后到達(dá) $(x,y)$ 的最小路徑是多少就行，直接乘以 $2$ 就是我們需要的答案了

所以直接迭代 $\frac{k}{2}$ 次，更新每個(gè)點(diǎn)的狀態(tài)即可，時(shí)間復(fù)雜度 $O(n?m?\frac{k}{2})$

最后提一句，第一種方法卡卡常是可以過的，因?yàn)榭吹搅饲芭糯罄泻臀宜悸芬粯?#xff0c;但我卻給寫T了，代碼放在后面，主要是展示思路

代碼：
AC代碼

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=510; const int b[4][2]={0,1,0,-1,1,0,-1,0}; int n,m,k; int raw[N][N],col[N][N];//raw[i][j]:(i,j)->(i,j+1) col[i][j]:(i,j)->(i+1,j) int dp[N][N][11]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);read(n),read(m),read(k);for(int i=1;i<=n;i++) {for(int j=1;j<m;j++) {read(raw[i][j]);}}for(int i=1;i<n;i++) {for(int j=1;j<=m;j++) {read(col[i][j]);}}if(k&1) {for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {printf("-1 ");}puts("");}return 0;}k/=2;for(int t=1;t<=k;t++) {for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {dp[i][j][t]=inf;for(int p=0;p<4;p++) {int xx=i+b[p][0];int yy=j+b[p][1];if(xx<=0||xx>n||yy<=0||yy>m) {continue;}int w;if(p==0) {w=raw[i][j];} else if(p==1) {w=raw[xx][yy];} else if(p==2) {w=col[i][j];} else if(p==3) {w=col[xx][yy];}dp[i][j][t]=min(dp[i][j][t],dp[xx][yy][t-1]+w*2);}}}}for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {printf("%d ",dp[i][j][k]);}puts("");}return 0; }

TLE代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=510; const int b[4][2]={0,1,0,-1,1,0,-1,0}; int n,m,k; int raw[N][N],col[N][N];//raw[i][j]:(i,j)->(i,j+1) col[i][j]:(i,j)->(i+1,j) int dp[N][N][11]; struct Node {int x,y,step; }; int solve(int x,int y,int k) {for(int t=0;t<=k;t++) {for(int i=max(x-t,1);i<=min(x+t,n);i++) {int d=t-abs(i-x);for(int j=max(y-d,1);j<=min(y+d,m);j++) {dp[i][j][t]=inf;}}}dp[x][y][0]=0;for(int t=1;t<=k;t++) {for(int i=max(x-t,1);i<=min(x+t,n);i++) {int d=t-abs(i-x);for(int j=max(y-d,1);j<=min(y+d,m);j++) {for(int p=0;p<4;p++) {int xx=i+b[p][0];int yy=j+b[p][1];if(xx<=0||xx>n||yy<=0||yy>m) {continue;}if(abs(xx-x)+abs(yy-y)>t-1) {continue;}int w;if(p==0) {w=raw[i][j];} else if(p==1) {w=raw[xx][yy];} else if(p==2) {w=col[i][j];} else if(p==3) {w=col[xx][yy];}dp[i][j][t]=min(dp[i][j][t],dp[xx][yy][t-1]+w);}}}}int ans=inf;for(int i=max(x-k,1);i<=min(x+k,n);i++) {int d=k-abs(i-x);for(int j=max(y-d,1);j<=min(y+d,m);j++) {ans=min(ans,dp[i][j][k]);}}return ans*2; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);read(n),read(m),read(k);for(int i=1;i<=n;i++) {for(int j=1;j<m;j++) {read(raw[i][j]);}}for(int i=1;i<n;i++) {for(int j=1;j<=m;j++) {read(col[i][j]);}}if(k&1) {for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {printf("-1 ");}puts("");}return 0;}for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {printf("%d ",solve(i,j,k/2));}puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1517D Explorer Space(dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。