简答题 偏难
#20024

划分字符串

划分字符串

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;vector&gt; using namespace std; const int N = 100005; int n; char s[N]; int a[N]; long long f[N]; int main() {     scanf("%d", &amp;n);     scanf("%s", s + 1);  // 字符串下标从1开始     for (int i = 1; i &lt;= n; ++i) {         scanf("%d", &amp;a[i]);     }     // DP:f[i] = 前i个字符分割后的最大收益     for (int i = 1; i &lt;= n; ++i) {         int mask = 0; // 位掩码,记录当前分段出现过的字符         // j向左枚举分段起点,区间 [j, i]         for (int j = i; j &gt;= 1; --j) {             int cur_bit = 1 &lt;&lt; (s[j] - 'a');             // 当前字符已在分段内,无法继续向左拓展             if (mask &amp; cur_bit) break;             mask |= cur_bit;             // 分段长度 len = i - j + 1             int seg_len = i - j + 1;             f[i] = max(f[i], f[j - 1] + a[seg_len]);         }     }     printf("%lld\n", f[n]);     return 0; }</pre>
这道题暂未补解析。