做网站有什么要求吗,用相片制作视频的软件,一个网站的建设步骤,太原网站建设方案服务链接#xff1a;
1444. 切披萨的方案数
题意#xff1a;
给定一个矩阵#xff0c;其中含有多个苹果#xff0c;需要切割k-1次,每次可以切割多行/多列#xff0c;需要保证切割两个部分都有苹果#xff0c;移除靠上/靠右的部分#xff0c;对留下部分进行后续的切割
1444. 切披萨的方案数
题意
给定一个矩阵其中含有多个苹果需要切割k-1次,每次可以切割多行/多列需要保证切割两个部分都有苹果移除靠上/靠右的部分对留下部分进行后续的切割求有几种切割方法
解
男人不能快算法需要快
这题需要通过两部分节约时间一部分是动态规划一部分是前缀和
这好像还是第一次写二维前缀和好像主要是要记得移除重复部分由于每次保留的是靠下/靠左的部分所以求的是已i j 为起点的右下角和
动态规划部分我们需要一个三维的DP[k][i][j]分别代表从i j开始的右下角矩阵成功切割k-1刀的方案数量
初始值是DP[1][i][j](sum[i][j] 0)即这一整块上存在苹果
递推公式需要判断行切和列切判断条件非常巧妙是整体苹果数量 切割后剩下的苹果数量公式是整体切割后的部分
整体DP[temp][i][j]假设在i2位置进行切割则判断sum[i][j] sum[i2][j]若为真即计算DP[temp][i][j]DP[temp-1][i2][j]要注意切割后所需的切割数-1
实际代码
#includebits/stdc.h
using namespace std;
constexpr static int Mod1E97;
int ways(vectorstring pizza, int k)
{int lgrowpizza.size(),lgcolpizza[0].length();vectorvectorintsum(lgrow1,vectorint(lgcol1));vectorvectorvectorintdp(k1,vectorvectorint(lgrow1,vectorint(lgcol1)));//初始化 for(int ilgrow-1;i0;i--){for(int jlgcol-1;j0;j--){sum[i][j]sum[i1][j]sum[i][j1]-sum[i1][j1](pizza[i][j]A);//二维前缀和 矩阵计算 dp[1][i][j]sum[i][j]0;}}//dp递推 for(int dp_k2;dp_kk;dp_k){for(int ilgrow-1;i0;i--){for(int jlgcol-1;j0;j--){//行切割for(int i2lgrow-1;i2i;i2--){if(sum[i][j]sum[i2][j])//切出来的有苹果{dp[dp_k][i][j]dp[dp_k-1][i2][j];dp[dp_k][i][j]%Mod;}}//列切割for(int j2lgcol-1;j2j;j2--){if(sum[i][j]sum[i][j2])//切出来的有苹果{dp[dp_k][i][j]dp[dp_k-1][i][j2];dp[dp_k][i][j]%Mod;}}}}}return dp[k][0][0];
}
int main()
{int k;cink;vectorstring pizza;string s;while(cins) pizza.push_back(s);int answays(pizza,k);coutansendl;return 0;
}限制
1 rows, cols 50rows pizza.lengthcols pizza[i].length1 k 10pizza 只包含字符 A 和 . 。
