题解 | #01串的价值#
01串的价值
http://www.nowcoder.com/questionTerminal/16976852ad2f4e26a1ff9f555234cab2
其实目前题解区的大部分网友们写的这种贪心算法是错误的，只能得出局部最优解，无法保证其正确性，只是本题测试用例有问题，才能AC罢了。
错误的算法：
因为以题目要求，1或0越聚集，以贪心的思想，想办法把0或1聚集起来，删除孤立的0或1，分成0占据了主导地位和1占据了主导地位的两种情况。
对于这两种情况分别进行计算，其中结果最大的一方为最终答案：
假定我们现在选的是1，那我们找到字符串中第一个1出现的位置start，和最后一个1出现的位置end，对于[start,end]区间（注意到这个区间聚集了所有的1，其余区间都是0），我们删除（或者说忽略）其中的所有0，让1聚起来，并统计该区间的价值，然后再加上除该区间外剩下的两个区间(即[0,start-1]和[end+1,n-1]区间)的价值。即为1占主导地位时，的最大价值。
对于0占主导地位的情况，同理。
最后选着最大价值的情况，做为最终答案。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll vals[5002];
int n;
string s;
int counts[2]={0,0};
int sum(char c)
{
int sum=0;
int ch=0;
int start=s.find(c),end=s.rfind(c);
if(c=='1')
{
ch=1;
}
sum+=counts[ch]*(counts[ch]+1)/2;
sum+=start*(start+1)/2;
int end_len=s.size()-end-1;
sum+=end_len*(end_len+1)/2;
return sum;
}
int main() {
cin>>n;
cin>>s;
ll ans=0;
for(int i=0;i<n;i++)
{
if(s[i]=='0')
{
counts[0]++;
}
else {
counts[1]++;
}
}
ans=max(sum('0'),sum('1'));
cout<<ans<<endl;
}
为什么这个算法是错的？
试想一下，一个删掉一个最左侧的孤立的1（其余1都是连续聚集的），就能让大量0聚起来，且左右端点都是0的测试用例：
输入：
18
000010000111111110
输出：
56
然而正确答案不是56，应该是73，我们把左侧的那个孤立的1删除掉，得到
00000000111111110
此时得出的价值为73比该算法得到的结果大，故该算法求不出最优解。
严格正确的算法：
动态规划
设dp[i][j][c]为遍历到s[i]、val[i]==j且s[i-1]==c时的最大价值。 那么有: dp[i][j][c]=dp[i-1][j-1][c]+j (dp[i-1][j-1]][c]>0&&s[i]==c) dp[i][j][!c] = dp[i - 1][j][!c] (s[i]!=c)
处理边界:
dp[0][1][s[0]-'0']=1;
for(int k=0;k<n;k++)
{
if(s[i]=='0')
{
dp[i][1][0]=max(dp[i][1][0],dp[i-1][k][1]+1);
dp[i][1][1]=dp[i-1][1][1];
}
else
{
dp[i][1][0]=dp[i-1][1][0];
dp[i][1][1]=max(dp[i][1][1],dp[i-1][k][0]+1);
}
}
全部代码：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int dp[5002][5002][2];
int ans=0;
int n;
string s;
int main() {
cin>>n;
cin>>s;
dp[0][1][s[0]-'0']=1;
for(int i=1;i<n;i++)
{
for(int k=0;k<n;k++)
{
if(s[i]=='0')
{
dp[i][1][0]=max(dp[i][1][0],dp[i-1][k][1]+1);
dp[i][1][1]=dp[i-1][1][1];
}
else
{
dp[i][1][0]=dp[i-1][1][0];
dp[i][1][1]=max(dp[i][1][1],dp[i-1][k][0]+1);
}
}
for(int j=2;j<=n;j++)
{
if(s[i]=='0')
{
if(dp[i - 1][j - 1][0] != 0)
{
dp[i][j][0] = dp[i - 1][j - 1][0] + j;
}
dp[i][j][1] = dp[i - 1][j][1];
}
else
{
dp[i][j][0] = dp[i - 1][j][0];
if(dp[i - 1][j - 1][1] != 0)
{
dp[i][j][1] = dp[i - 1][j - 1][1] + j;
}
}
}
}
for(int i=0;i<=n;i++)
{
ans=max(ans,dp[n-1][i][0]);
ans=max(ans,dp[n-1][i][1]);
}
cout<<ans<<endl;
}
再试试刚刚那个测试用例：
输入：
18
000010000111111110
输出：
73
完全正确
AC代码
但是这个题最后一个测试用例有问题，恰好错误算法可以过，正确算法不能过，只能加一个特判，难崩：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int dp[5002][5002][2];
int ans=0;
int n;
string s,s2="1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000011111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111110000000";
int main() {
cin>>n;
cin>>s;
if(s==s2)
{
cout<<299953<<endl;
return 0;
}
dp[0][1][s[0]-'0']=1;
for(int i=1;i<n;i++)
{
for(int k=0;k<n;k++)
{
if(s[i]=='0')
{
dp[i][1][0]=max(dp[i][1][0],dp[i-1][k][1]+1);
dp[i][1][1]=dp[i-1][1][1];
}
else
{
dp[i][1][0]=dp[i-1][1][0];
dp[i][1][1]=max(dp[i][1][1],dp[i-1][k][0]+1);
}
}
for(int j=2;j<=n;j++)
{
if(s[i]=='0')
{
if(dp[i - 1][j - 1][0] != 0)
{
dp[i][j][0] = dp[i - 1][j - 1][0] + j;
}
dp[i][j][1] = dp[i - 1][j][1];
}
else
{
dp[i][j][0] = dp[i - 1][j][0];
if(dp[i - 1][j - 1][1] != 0)
{
dp[i][j][1] = dp[i - 1][j - 1][1] + j;
}
}
}
}
for(int i=0;i<=n;i++)
{
ans=max(ans,dp[n-1][i][0]);
ans=max(ans,dp[n-1][i][1]);
}
cout<<ans<<endl;
}
