「Codeforces 1107E」Vasya and Binary String

发表于 | | 阅读次数:
字数统计: 570 字

Description

题目链接：Codeforces 1107E

Vasya 有一个长度为 $n$ 的 $01$ 串 $s$，他还有一个长度为 $n$ 的序列 $a_i$。

Vasya 每次会从这个字符串中删除一段连续的相同字符，直到这个字符串为空。如果他删除了一段长度为 $x$ 的子串，他将得到 $a_x$ 的分数。

请你求出 Vasya 的最大得分。

数据范围：$1\le n\le 100$，$1\le a_i\le 10^9$

Solution

首先我们肯定想到 $\text{DP}$，而这题就难在定义 $\text{DP}$ 状态。

我们可以发现，无论我们怎么删除，肯定都可以转化为删除若干个完整的区间，于是可以想到 $f_{i,j}$ 表示删除 $[i,j]$ 这个区间的最大价值。

由于删除的价值和相同的长度有关，那么我们把长度设计进状态：$f_{i,j,k}$ 表示考虑区间 $[i,j]$，在 $j$ 右侧（不包括 $j$）有连续 $k$ 个和 $s_j$ 相同的数字。

状态 $f_{l,r,k}​$ 的转移方程如下：

  • 如果我们直接把 $r$ 和后面的 $k$ 个直接删除，那么答案为 $f_{l,r-1,0}+a_{k+1}$。
  • 如果我们考虑把 $[l,r]$ 内部的一个区间 $[i+1,r-1]$ 删除并对整个区间没有影响（即满足 $s_i=s_r$，使得区间 $(i,r)$ 不会被左右端点 $i,r$ 删去），那么对于剩下的区间 $[l,i]$ 的右侧除了原来的 $k$ 个相同字符，还多了一个 $s_r$。答案为 $f_{l,i,k+1}+f_{i+1,r-1,0}​$。

为了使代码难度降低，我们可以采用记忆化搜索。

时间复杂度：$O(n^4)​$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=105;
int n,a[N];
long long f[N][N][N];
char s[N];

long long dfs(int l,int r,int k) {
    if(l>r) return 0;
    if(l==r) return a[k+1];
    if(~f[l][r][k]) return f[l][r][k];
    long long &ans=f[l][r][k]=dfs(l,r-1,0)+a[k+1];
    for(int i=l;i<r;++i) {
        if(s[i]==s[r]) ans=std::max(ans,dfs(l,i,k+1)+dfs(i+1,r-1,0));
    }
    return ans;
}
int main() {
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    memset(f,-1,sizeof(f));
    printf("%lld\n",dfs(1,n,0));
    return 0;
}
0%