题目链接
题目传送门 https://www.luogu.org/problem/P4850
题目解析
这里介绍一种不用开 \(O2\) 的方法
这题的 dp 方程很好推:
\(f[x_1][y_1][x_2][y_2]=min(f[x_1][y_1][x_2][y_2],f[x_1][y_1][i][y_2]+f[i+1][y_1][x_2][y_2]+s[x_1][y_1][x_2][y_2])\)
以及:
\(f[x_1][y_1][x_2][y_2]=min(f[x_1][y_1][x_2][y_2],f[x_1][y_1][x_2][i]+f[x_1][i+1][x_2][y_2]+s[x_1][y_1][x_2][y_2])\)
具体的数组含义看代码就懂了
然后打个记忆化搜索上去 --\(TLE\) 了
我们发现四维数组的访问很慢, 所以可以用类似哈希的方法将四维转化为一维
然后就卡 cao 过去了
代码
- #include <stdio.h>
- using namespace std;
- template <typename T> inline void Read(T &t)
- {
- int c=getchar(),f=0;
- for (;c<'0'||c>'9';c=getchar()) f=(c=='-');
- for (t=0;c>='0'&&c<='9';c=getchar()) t=(t<<3)+(t<<1)+(c^48);
- if (f) t=-t;
- }
- const int N=55,t[]={1,55,3025,166375,9150625};
- int n,m,s[N][N];
- int dp[N*N*N*N];
- inline int min(int a, int b) {return a<b?a:b;}
- int dfs(int x, int y, int _x, int _y)
- {
- int a=x*t[3]+y*t[2]+_x*t[1]+_y*t[0];
- if (dp[a]) return dp[a];
- if (x==_x&&y==_y) return 0;
- dp[a]=0x7fffffff;
- for (int i=x;i<_x;i++)
- dp[a]=min(dp[a],dfs(x,y,i,_y)+dfs(i+1,y,_x,_y));
- for (int i=y;i<_y;i++)
- dp[a]=min(dp[a],dfs(x,y,_x,i)+dfs(x,i+1,_x,_y));
- return dp[a]+=s[_x][_y]-s[x-1][_y]-s[_x][y-1]+s[x-1][y-1];
- }
- int main()
- {
- Read(n),Read(m);
- for (int i=1;i<=n;i++)
- for (int j=1;j<=m;j++)
- Read(s[i][j]),s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
- printf("%d\n",dfs(1,1,n,m));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3209222.html