题目:https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_d
题意:给一个 01 串,每次可以把 101
换成 010
,问最多能换多少次 .
题解:
令 \(dp_i\) 表示 \(1\sim i\) 最多换多少次,记录一个 \(l_i\) 表示 \(i\) 左边最接近的 \(0\),\(r_i\) 表示 \(i\) 右边最接近的 \(0\),从而:
\[dp_i=\max\begin{cases}dp_{i-1}\\dp_{l_{i-3}+1}+i-l_{i-3}-3&i\ge 3 且 s_{i-3},s_{i-2},s_{i-1} 构成一个\tt 101&\qquad (1)\\dp_{l_{i-3}+2}+i-l_{i-3}-4&(1) 且 l_{i-3}\neq i-4\end{cases} \] \[dp_{l_{i-3}}=\max\{dp_{i}+l_{i-3}-i-2\quad i+3\le n 且s_{i},s_{i+1},s_{i+2}构成一个\tt 101 \qquad\rm (2)\qquad\,\} \] \[dp_{l_{i-3}-1}=\max\{dp_{i}+l_{i-3}-i-3\quad(2) 且 l_{i-3}\neq i+3\} \]对于每一行的解释:
- 第一行:显然
- 第二行:若目前有 \(\tt 101\),则换
- 第三行:若换完还有 \(\tt101\),再换
- 第四、五行:同第二、三行 .
Code:
using namespace std;
const int N=500500;
int n,dp[N],l[N],r[N];
string s;
int main()
{
scanf("%d",&n); cin>>s;
l[0]=(s[0]=='0'?0:-1); r[n]=n;
for (int i=1;i<n;i++)
if (s[i]=='1') l[i]=l[i-1];
else l[i]=i;
for (int i=n-1;i>=0;i--)
if (s[i]=='1') r[i]=r[i+1];
else r[i]=i;
for (int i=0;i<=n;i++)
{
if (i) dp[i]=max(dp[i],dp[i-1]); // because line 47 .
if ((i>=3)&&(s[i-1]=='1')&&(s[i-2]=='0')&&(s[i-3]=='1')) // pre
{
int j=l[i-3];
dp[i]=max(dp[i],dp[j+1]+i-j-3);
if (j!=i-4) dp[i]=max(dp[i],dp[j+2]+i-j-4); // 101 * 2
}
if ((i+3<=n)&&(s[i]=='1')&&(s[i+1]=='0')&&(s[i+2]=='1')) // suc ( nxt )
{
int j=r[i+2];
dp[j]=max(dp[j],dp[i]+j-i-2);
if (j!=i+3) dp[j-1]=max(dp[j-1],dp[i]+j-i-3); // 101 * 2;
}
} printf("%d",dp[n]);
return 0;
}