题目描述
给你一个下标从0开始的 二进制字符串floor,它表示地板上砖块的颜色。
floor[i] = ‘0’表示地板上第i块砖块的颜色是 黑色。
floor[i] = ‘1’表示地板上第i块砖块的颜色是 白色。
同时给你numCarpets 和carpetLen。你有numCarpets条黑色的地毯,每一条黑色的地毯长度都为carpetLen块砖块。请你使用这些地毯去覆盖砖块,使得未被覆盖的剩余 白色砖块的数目 最小。地毯相互之间可以覆盖。
返回没被覆盖的白色砖块的 最少数目。
题解
这是今天双周赛的D题。
这个题经历了很长的心路历程,先想了贪心策略,即每次用滑动窗口求最大覆盖,然后贪线段数量次。然后想了一个贪心的反例,比如串是”0111110000111110”,线段长为8,有两条线段,这样我们实际上可以覆盖所有的0,但是贪心会先盖住中间的部分。
然后室友说特判一下 线段长 * 线段数目 >= 最后一个0 和 第一个0 的距离应该就可以过了,于是就去写了贪心,然后真的一次就过了。于是就开开心心地去做毕设了。
之后逛评论区,发现了可以hack的样例,比如串是”0110000110111011011”,线段长度为5,共2个线段,答案实际上是可以覆盖6个0,而如果贪心只能覆盖5个。
那么它实际上是个dp,被室友坑了(不是)。
考虑dp[i][j]表示覆盖前j块砖用i个线段的最少剩余白砖数目。那么转移公式应该是
$$ dp[i][j] = min(dp[i][j - 1] + a[i] == ‘1’, dp[i - 1][j - len]) $$
那我们发现它实际上和背包的转移公式很像,就可以把第二维像背包一样用滚动数组优化。
具体的代码明天补一下。
UPD220320:代码
const int maxn = 1e3 + 10;
class Solution {
public:
int dp[maxn][maxn];
int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
int lenf = floor.length();
for(int j = 1; j <= lenf; j++){
dp[0][j] = dp[0][j - 1] + (floor[j - 1] == '1');
}
for(int i = 1; i <= numCarpets; i++){
for(int j = 1; j <= lenf; j++){
dp[i][j] = dp[i][j - 1] + (floor[j - 1] == '1');
if(j >= carpetLen) dp[i][j] = min(dp[i][j], dp[i - 1][j - carpetLen]);
else dp[i][j] = 0;
}
}
return dp[numCarpets][lenf];
}
};