P5650

·Ansel · 2019-11-14 20:39:18 · 题解

Ansel又双叒叕的来发题解了

Ansel这几天疯狂再写DP所以看啥都像DP

OK废话不多说直接进入正题【捂脸】

Idea:

• 首先我看到这个题第一反应是这道题有点像01背包问题，（第一反应其实是这是啥鬼题( :∇:) ），我的考虑是从串的第一个字符开始扫描，然后考虑是否添加下一个字符，如果添加了对整体，之前的串会有所帮助那就要，如果没有帮助就不要
• 如果不理解的话可以去学习一下背包问题（背包问题分为很多种，01背包问题也是背包问题中最简单也是最基础的DP入门问题），大家如果不嫌弃Ansel这个蒟蒟的话可以关注一下我的博客，之后会不断补充与完善一系列的博客讲解，Ansel愿与大一起进步

• 注意！！ : 记得要考虑当所有的字符都为0的时候进行特判（Ansel在这个点卡了好久【吐血】）

  下面给出状态转移方程

  if (str[i] == '0') a[i] = a[i-1] + 1;
  else a[i] = max(a[i-1]-1,a[i]);

  解释

1. 如果下一个字符是 0 的话直接添加（不解释）
2. 下一个字符如果为 1 ，那么就考虑添加该点则最高子串的值减小1，与不添加该点进行对比选取最大

3. 千万记住进行特判如果全为1的话，那么就是0 - 1 = -1，最终结果为-1

   最后献上AC代码

   #include <cstdio>
   #include <iostream>
   #include <algorithm>
   #include <cstring>
   using namespace std;
   int const maxn = 1e5+10;
   string str;
   int a[maxn];
   int main() 
   {
   int flag = 0;
   int ans = -999;
   cin >> str;
   int len = str.length();
   for (register int i = 0; i < len; i++)
   {
       if (str[i] == '0') a[i] = a[i-1] + 1;
       else a[i] = max(a[i-1]-1,a[i]);
   
   }
   for (register int i = 1; i <= len; i++)
   {
       if (a[i] > ans ) ans = a[i];
   }
   for (register int i = 0; i < len; i++)
   {
       if (str[i]=='1') flag++;
   }
   if (flag == len)
   {
       cout << "-1" <<endl;
       return 0;   
    } 
   cout << ans << endl;
   }

   如果Ansel有不对的地方，或没有解释清楚的地方，欢迎留言与大家一起进步！

   Ps： 溜了溜了orz！