Codeforces 1107E（区间dp）

用solve(l, r, prefix)代表区间l开始r结束、带了prefix个前缀str[l]（即l前面的串化简完压缩成prefix-1个str[l]，加上str[l]共有prefix个）的最大值。

每层可以选择：

1.直接“提现”，把起始位和前面的“存款”直接提出来，再计算l+1～r区间的值；

2.继续“存款”，枚举和str[l]相同的位置，把中间先合并了然后删了，把prefix+1，即把枚举的这位和之前的存款粘在一起，然后计算i～r的值，更新ans。

乍一想会觉得每次只把两个粘在一起这行吗，实际上一个区间里可能会好几个粘在一起啊？但其实：假设i < j，算i的时候i～r的那部分的存款就为prefix+1了，即我们选取j的时候，i已经在里了，所以只是子区间看起来选两个而已，实际上从大的范围来看已经选了若干个。

然后这个方法居然不用提前预处理——真·a[i]，可能是搞的过程中就背包了吧？只是预处理的会跑得快一些。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 int n;

 ll a[], dp[][][];

 char s[];

 ll solve(int l, int r, int prefix) {

     if (l > r)

         return ;

     if (l == r)

         return a[prefix];

     ll &ret = dp[l][r][prefix];

     if (ret)

         return ret;

     ret = a[prefix] + solve(l + , r, );

     for (int i = l + ; i <= r; i++) {

         if (s[i] == s[l])

             ret = max(ret, solve(l + , i - , ) + solve(i, r, prefix + ));

     }

     return ret;

 }

 int main() {

     cin >> n >> (s + );

     for (int i = ; i <= n; i++)

         cin >> a[i];

     for (int i = ; i <= n; i++) {

         for (int j = i; j > ; j--) {

             a[i] = max(a[i], a[j] + a[i - j]);

         }

     }

     cout << solve(, n, ) << endl;

     return ;

 }

巴特西

Codeforces 1107E（区间dp）

最新文章

热门文章