实际上切出来的矩阵在原矩阵上的位置是不重要的。。。重要的只有矩阵的大小和上下左右是否在边界上。
于是我们可以设f[x][y][l][r][u][d]表示x*y的矩阵上下左右是不是边界的最小代价。
记忆化搜索一下横着切和竖着切。
但是这样会被卡。。我们令x>=y l>=r u>=d可以减少很多相同的状态数，而且答案是不变的，这样常数小很多才能过
#include#include #include #include #include #define ll long long using namespace std;const int maxn=310;int n,m,k;ll f[maxn][maxn][2][2][2][2];void read(int &k){ int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f;}ll dfs(int x,int y,int l,int r,int u,int d){ if(x