B. Array Walk

题意：给定一个长度为\(n\)的序列，从下标1开始，走\(k\)步，其中最多\(z\)步向左。每走到一个位置就取一次这个位置的数。问可以取到的最大总和是多少。

思路：考虑dp，\(dp[i][j]\)表示走了\(i\)步，\(j\)步为向左时的最大总和。则当\(dp[i][j]\)可以由走了\(i-1\)步、现在向右走以及走了\(i-1\)步、现在向左走这两个状态转移而来

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define mst(a, b) memset((a), (b), sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef, mid, rt << 1
#define rson mid + 1, rig, rt << 1 | 1
const int maxn = 1e5 + 5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int a[maxn], dp[maxn][6];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, k, z;
        scanf("%d %d %d", &n, &k, &z);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        dp[0][0] = a[1];
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j <= z; j++) {
                dp[i][j] = dp[i - 1][j] + a[1 + i - 2 * j];
                if (j > 0)
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[1 + i - 2 * j]);
            }
        }
        int ans = 0;
        for (int j = 0; j <= z; j++) {
            ans = max(ans, dp[k][j]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Good String

题意：如果将一个字符串循环左移一位与循环右移一位后，得到的两个新字符串相等，则称该字符串为good string。给定一个字符串\(s\)，问需要至少删除\(s\)中多少个字符，才能使其变成good string。

思路：容易发现，good string只有两种情况：1、整个字符串只有一种字符；2、字符串形如\(ababab...\)，且长度为偶数。对于第一种情况，只需要找出出现次数最多的字符即可；对于第二种情况，因为字符只有10种，暴力枚举一下可以组成good string的两种字符就行。

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define mst(a, b) memset((a), (b), sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef, mid, rt << 1
#define rson mid + 1, rig, rt << 1 | 1
const int maxn = 2e5 + 5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char s[maxn];
int cnt[10] = { 0 };
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        mst(cnt, 0);
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        for (int i = 1; i <= len; i++) {
            cnt[s[i] - '0']++;
        }
        int maxi = 0;
        for (int i = 0; i <= 9; i++) {
            maxi = max(maxi, cnt[i]);
        }
        int ans2 = 0;
        for (int i = 0; i <= 9; i++) {
            for (int j = 0; j <= 9; j++) {
                int l=0;
                for(int k=1;k<=len;k++){
                    if(l%2==0){
                        if(s[k]==i+'0') l++;
                    }else{
                        if(s[k]==j+'0') l++;
                    }
                }
                if(l&1) l--;
                ans2=max(ans2,l);
            }
        }
        //printf("ans2 = %d\n", ans2);
        ans2 = len - ans2;
        int ans1 = len - maxi;
        printf("%d\n", min(ans2, ans1));
    }
    return 0;
}