【每日一题】3月11日[HAOI2016]字符合并

题意

给出一个长度为 $n$ 的01串然后将相邻的 $k$ 个字符合并得到一个新的字符并且获得一定的分数

解释一下样例 101 合并后面的01 得到一个1 然后分数是10 然后就变成11了再合并11 就得到一个 1分数是30 所以总的分数就是40

设 $dp[i][j][k]$ 为在范围 $\left\{ i , j \right\}$ 状态为s的最大的值在 $\left\{ i , j \right\}$ 之间我们都以m为长度将每一个都合并那么 $k$ 我们通过枚举，每次中间的分割点因为只能每 $m$ 个合成一个字母，所以每次就把分割点往前推 $m-1$ 个距离。并且合并之后的区间 $\left\{ i , j \right\}$ 就会变成 $c_k$ 了

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
const int N = 300 + 7;
const int INF = 0x3f3f3f3f;
ll w[1 << 8] , dp[N][N][1 <<8];
ll c[1 << 8];
char s[N];
ll  n , m;

void solve(){
    memset(dp , -0x3f , sizeof(dp));
    n = read() , m = read();
    scanf("%s" , s + 1);
    int sz = 1 << m ;
    for(int i = 0 ; i <= sz - 1 ; ++i){
        c[i] = read() , w[i] = read();
    }
    for(int i = 1 ; i <= n ; ++i){
        dp[i][i][s[i] - '0'] = 0;
    }
    for(int len = 2 ; len <= n ; ++len){
        for(int i = 1 , j = len ; j <=n ; ++i , ++j){
            int x = (len - 1 ) % (m - 1) + 1;
            if(x == 1){
                for(int k = 0 ; k < sz ; ++k){
                    for(int l = j - 1 ; l >= i ;l -= m - 1){
                        dp[i][j][c[k]] = max(dp[i][j][c[k]], dp[i][l][k >> 1] + dp[l + 1][j][k & 1] + w[k]);
                    }
                }
            }
            else{
                for(int k = 0 ; k < 1 << x ; ++k){
                    for(int l = j - 1 ; l >= i ; l -= m - 1)
                        dp[i][j][k] = max(dp[i][j][k] , dp[i][l][k >> 1] + dp[l + 1][j][k & 1]);
                }
            }
        }
    }
    ll ans = 0 ;
    for(int i = 0 ; i < sz - 1 ; ++i){
        ans = max(ans , dp[1][n][i]);
    }
    printf("%lld\n" , ans);
}

int main(void){
    solve();

    return 0;
}