周赛 – 188 – 切披萨的方案数

不知道之前错在哪里了,感觉思路没问题就是WA,睡了午觉起来清空了代码重写了一遍就过了(瘫。

4. 切披萨的方案数

给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。
切披萨的每一刀,先要选择是向垂直还是水平方向切,再在矩形的边界上选一个切的位置,将披萨一分为二。如果垂直地切披萨,那么需要把左边的部分送给一个人,如果水平地切,那么需要把上面的部分送给一个人。在切完最后一刀后,需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字,请你返回它对 10^9 + 7 取余的结果。

样例

示例 1:

输入:pizza = [“A..”,”AAA”,”…”], k = 3
输出:3
解释:上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。

示例 2:

输入:pizza = [“A..”,”AA.”,”…”], k = 3
输出:1

示例 3:

输入:pizza = [“A..”,”A..”,”…”], k = 1
输出:1

提示

  • 1 <= rows, cols <= 50
  • rows == pizza.length
  • cols == pizza[i].length
  • 1 <= k <= 10
  • pizza 只包含字符 ‘A’ 和 ‘.’ 。

思路

看到这么小的数据范围就想到了区间DP。

【状态表示】

题目中说每次把左边或者上面的一块分出去,意味着剩下的永远是右下角的一块,可以用左上角坐标唯一代替。

dp[k][i][j] 表示切了 k 刀,剩余的蛋糕左上角坐标为 (i, j) 的方案数。

【状态转移】

分两种情况:

  • 如果是横着切一刀,那么 dp[k][i][j] 可以从 dp[k-1][ii][j] 转移过来,其中 ii∈[0, i) ,转移条件是在 iii∈[ii, i)jjj∈[j, m) 的矩形披萨中存在苹果。
  • 如果是横着切一刀,那么 dp[k][i][j] 可以从 dp[k-1][i][jj] 转移过来,其中 jj∈[0, j) ,转移条件是在 jjj∈[jj, j)iii∈[i, n) 的矩形披萨中存在苹果。

【初始化】

dp 数组清空为 0dp[0][0][0] = 1

代码

int dp[15][55][55];
const int MOD = 1e9 + 7;
class Solution {
public:
    int ways(vector<string>& pizza, int k) {
        int n = pizza.size(), m = pizza[0].size();
        memset(dp, 0, sizeof(dp)); dp[0][0][0] = 1;
        
        for(int l=1; l<k; l++) {
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    int sum = 0;
                    for(int ii=i-1; ii>=0; ii--) {
                        for(int jj=j; jj<m; jj++) if(pizza[ii][jj] == 'A') sum++;
                        if(sum > 0) dp[l][i][j] = (dp[l][i][j] + dp[l-1][ii][j]) % MOD;
                    }
                    sum = 0;
                    for(int jj=j-1; jj>=0; jj--) {
                        for(int ii=i; ii<n; ii++) if(pizza[ii][jj] == 'A') sum++;
                        if(sum > 0) dp[l][i][j] = (dp[l][i][j] + dp[l-1][i][jj]) % MOD;
                    }
                }
            }
        }
        
        int ans = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                int sum = 0;
                for(int ii=i; ii<n; ii++) {
                    for(int jj=j; jj<m; jj++) {
                        if(pizza[ii][jj] == 'A') sum++;
                    }
                }
                if(sum > 0) ans = (ans + dp[k-1][i][j]) % MOD;
            }
        }
        return ans;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇