C++前缀和算法的应用：用地毯覆盖后的最少白色砖块 原理源码测试用例

class Solution {
public:
int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
//错误想法：如果盖毯子，则毯子的末端一定盖住白砖
//计算最多可以盖住多少块白砖
vector vSum = { 0 };//vSum[i]表示 floor[0,i)中白砖的数量
for (const char& ch : floor)
{
vSum.emplace_back(vSum.back() + (‘1’ == ch));
}
m_c = floor.length();
vector pre (m_c+1,0);//表示i块毯子，覆盖了[0,i)，能盖住的最多白砖数
for (int i = 0; i < numCarpets; i++)
{
vector dp = pre;
for (int iPre = 0; iPre < pre.size(); iPre++)
{
const int iNew = min(m_c , iPre + carpetLen);
dp[iNew] = max(dp[iNew], pre[iPre] + (vSum[iNew]-vSum[iPre]));
}
for (int i = 0; i < m_c; i++)
{
dp[i + 1] = max(dp[i], dp[i + 1]);
}
pre.swap(dp);
}
return vSum.back() - *std::max_element(pre.begin(),pre.end());
}
int m_c;
};

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
Solution slu;
string floor = “10110101”;
int numCarpets = 2, carpetLen = 2;
int res;

class Solution {
public:
int minimumWhiteTiles(const string floor, const int numCarpets, const int carpetLen) {
m_c = floor.length();
//dp[i][j] 已经处理了i块砖，用了j块地毯，最少为覆盖的砖数
vector<vector> dp(m_c+1, vector(numCarpets+1,INT_MAX));
dp[0][0] = 0;
for (int brick = 0; brick < m_c; brick++)
{
for (int iUseCarpets = 0; iUseCarpets <= numCarpets; iUseCarpets++)
{
const int& iValue = dp[brick][iUseCarpets];
if (INT_MAX == iValue)
{
continue;
}
//空一格
dp[brick + 1][iUseCarpets] = min(dp[brick + 1][iUseCarpets], iValue + (‘1’ == floor[brick]));
//假定不重叠，如果重叠右移到不重叠，不影响结果
if (numCarpets == iUseCarpets)
{
continue;
}
const int iNewBrick = min(brick + carpetLen, m_c);
dp[iNewBrick][iUseCarpets + 1] = min(dp[iNewBrick][iUseCarpets + 1], iValue);
}
}
return *std::min_element(dp[m_c].begin(), dp[m_c].end());
}
int m_c;
};