厦门同安影视城好玩吗,室内装饰风水,哈市公交线路查询
目录
方法一:四维dp
设$\text{dp[i][j][k][l]}$表示第一个人走到了$(i,j)$第二个人走到了$(k,l)$的位置时的最大和,因为可以向下走也可以向右走所以$\text{dp[i][j][k][l]=max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])}$$+(i,j)$和$(k,l)$位置的数如果$i=k$并且$j=l$要减去一个。
时间复杂度为$o(n^4)$
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> using namespace std; int n,map[10][10],dp[10][10][10][10]; //dp[i][j][k][l]表示第一个人走到了(i,j)第二个人走到了(k,l)的位置时的最大和 inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } int main(){ n=read(); int x,y,w; while(1){ x=read(),y=read(),w=read(); if(!x&&!y&&!w) break; map[x][y]=w; } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ for(int k=1;k<=n;++k){ for(int l=1;l<=n;++l){ dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+map[i][j]+map[k][l]; if(i==k&&j==l) dp[i][j][k][l]-=map[i][j]; } } } } printf("%d\n",dp[n][n][n][n]); return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论