B-string value (string DP) of the 16th Northeast College Students' Programming Competition (warm-up)

TP

The question ：

• Given a string , Find all of this string Continuous substrings in , The maximum number of characters minus the minimum number of characters Value What's the biggest .

Ideas ：

• dp, String type , Try and 26 Letter connection
• $\mid s\mid \le 10^6$ , Pay attention to memory limitations .

Two codes , Detail Notes .

$Code:$

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define oper(a) operator<(const a& ee)const
#define endl '\n'
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e8;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
int dp[2][26][26];
// Just look at the words of the last two ,dp[j][k]  representative   front  i  In all consecutive substrings formed by bits ,
//j  Most characters appear ,k  The maximum difference in the case of the least number of characters 

// Just look at the first place ,dp[0]  The collection is  j、k  Characters may not exist ,
//dp[1]  Collected information ,j、k  All characters must exist , In this way, the maximum difference is legal 
char s[N];

void solve() {
    
    cin >> s + 1;
    n = strlen(s + 1);

    int ans = 0;
    mem(dp[1], -0x3f);// None of the initial characters exist , illegal 

    for (int i = 1; i <= n; i++) {
    
        int u = s[i] - 'a';
        // What is the current character , Corresponding to the status of the affected part 

        for (int j = 0; j < 26; j++) {
    
            if (u == j)continue;// The same is meaningless 
            // There are now  u ,u、j  State maximum difference ++

            dp[0][u][j]++;
            dp[1][u][j]++;
            ans = max(ans, dp[1][u][j]);// Maintain the optimal solution at any time 
        }

        for (int j = 0; j < 26; j++) {
    
            if (u == j)continue;
            // There are now  u ,j、u  State maximum difference --

            dp[1][j][u]--;
            dp[1][j][u] = max(dp[1][j][u], dp[0][j][u] - 1);
            // Once there was one  u, Accumulated after  j、u  The state can be legal 
            // from  dp[0]  Assign to  dp[1]

            dp[0][j][u] = max(dp[0][j][u] - 1, 0);
            // dp[0]  There is no need to maintain negative numbers 
        }
    }

    cout << ans;
}

int main() {
    
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++)
        solve();
    return 0;
}
/* */

$Code:$

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define oper(a) operator<(const a& ee)const
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
struct node
{
    
    int w, f1, f2;
}dp[26][26];
char s[N];

void solve() {
    
    cin >> s + 1;
    n = strlen(s + 1);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
    
        int u = s[i] - 'a';

        for (int j = 0; j < 26; j++) {
    
            if (u == j)continue;

            dp[u][j].w++;
            if (dp[u][j].f1)ans = max(ans, dp[u][j].w);
            //f1  Mark  j  Whether the character exists , There is no answer that cannot be counted 

            dp[j][u].w = max(dp[j][u].w - 1, -1);
            // The shortest time is  -1, There is only one  u  Character as the beginning , No matter how short it is 

            dp[j][u].f1 = 1;//u  Characters exist 

            if (dp[j][u].w == -1)dp[j][u].f2 = 1;// If  u  The beginning of the character is marked with 
            else if (dp[j][u].f2) {
    

                // Meet again after  u  Character time , Obviously the first one  u  You can give up , Also does not affect the  u  The existence of characters 

                dp[j][u].w++;// length ++
                dp[j][u].f2 = 0;
            }
        }
    }

    cout << ans;
}

int main() {
    
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++)
        solve();
    return 0;
}
/* */