Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531119535000,"title":"A - Working out ","dislikeCnt":1,"content":"最多两个点同时重合\n```\n#include\u003ciostream\u003e\n#include\u003ccstdio\u003e\n#include\u003ccstring\u003e\n#include\u003calgorithm\u003e\nusing namespace std;\nint dp1[1010][1010],dp2[1010][1010],dp3[1010][1010],dp4[1010][1010],a[1010][1010],m,n;\nint main(){\n scanf(\"%d %d\",\u0026n,\u0026m);\n for(int i\u003d1;i\u003c\u003dn;i++)\n for(int j\u003d1;j\u003c\u003dm;j++)\n scanf(\"%d\",\u0026a[i][j]); //储存矩阵 \n for(int i\u003d1;i\u003c\u003dn;i++)\n for(int j\u003d1;j\u003c\u003dm;j++)\n dp1[i][j]\u003dmax(dp1[i-1][j],dp1[i][j-1])+a[i][j];//由(1,1)到(m,n)的最大值 \n for(int i\u003dn;i\u003e\u003d1;i--)\n for(int j\u003dm;j\u003e\u003d1;j--)\n dp2[i][j]\u003dmax(dp2[i][j+1],dp2[i+1][j])+a[i][j];//由(m,n)到(1,1)的最大值\n for(int i\u003dn;i\u003e\u003d1;i--)\n for(int j\u003d1;j\u003c\u003dm;j++)\n dp3[i][j]\u003dmax(dp3[i][j-1],dp3[i+1][j])+a[i][j];//由(1,n)到(m,1)的最大值\n for(int i\u003d1;i\u003c\u003dn;i++)\n for(int j\u003dm;j\u003e\u003d1;j--)\n dp4[i][j]\u003dmax(dp4[i][j+1],dp4[i-1][j])+a[i][j];//由(m,1)到(1,n)的最大值\n int ans\u003d0;\n for(int i\u003d2;i\u003cn;i++){\n for(int j\u003d2;j\u003cm;j++){\n ans\u003dmax(ans,dp1[i][j-1]+dp2[i][j+1]+dp3[i+1][j]+dp4[i-1][j]);//枚举所有可能重合的点,取最大值 \n ans\u003dmax(ans,dp1[i-1][j]+dp2[i+1][j]+dp3[i][j-1]+dp4[i][j+1]);\n }\n }\n printf(\"%d\\n\",ans);\n return 0;\n}\n```","threadId":31186,"likeCnt":1,"createTime":1531119535000,"isWorkbook":false,"viewCnt":1858,"openness":2,"fav":false,"id":494,"trustable":false}