Loading [MathJax]/jax/output/CommonHTML/fonts/TeX/AMS-Regular.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >CF1409F「Subsequences of Length Two」

CF1409F「Subsequences of Length Two」

作者头像
hotarugali
发布于 2022-03-02 12:23:02
发布于 2022-03-02 12:23:02
30400
代码可运行
举报
运行总次数:0
代码可运行

1. 题目

题目链接:CF1409F「Subsequences of Length Two」

Description

You are given two strings and consisting of lowercase Latin letters. The length of ttt is(this string consists only of two characters).

In one move, you can choose any character of s and replace it with any lowercase Latin letter. More formally, you choose some and replace (the character at the position ) with some character from 'a' to 'z'.

You want to do no more than replacements in such a way that maximizes the number of occurrences of in as a subsequence.

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input

The first line of the input contains two integers nnn and () — the length of and the maximum number of moves you can make. The second line of the input contains the string consisting of nnn lowercase Latin letters. The third line of the input contains the string consisting of two lowercase Latin letters.

Output

Print one integer — the maximum possible number of occurrences of t in as a subsequence if you replace no more than characters in optimally.

Examples

input #1
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
4 2
bbaa
ab
output #1
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
3
input #2
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
7 3
asddsaf
sd
output #2
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
10
input #3
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
15 6
qwertyhgfdsazxc
qa
output #3
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
16
input #4
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
7 2
abacaba
aa
output #4
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
15

2. 题解

分析

一般这种最优计数问题应该想到使用dp,但是 dp最困难的在于构造状态以及状态转移方程。对于这道题的dp 构造,蒟蒻的我毫无头绪,只好看比赛题解(Orz)。

  • 首先定义状态:dp(i,j,u)表示处理完字符串 s的第 i个字符后,已经使用了jmove操作,且字符串s[0..i1]中有u个字符t[0],此时字符串s[0..i1]中包含的子序列 t 的最大个数。
  • 然后构造状态转移方程:设 e0=1表示 s[i]=t[0],否则e0=0;设 e1=1表示 s[i]=t[1],否则e1=0;设 e01=1表示t[0]=t[1],否则 e01=0
  1. 如果不处理第 iii 个字符,则有:
  2. 如果将第 i个字符替换为 t[0],则有:
  3. 如果将第 i个字符替换为t[1],则有:

构造出了转移方程后,最重要的是确定边界。首先易知的是对于第 2 和 3 个方程,要求 j<k;然后是初始条件 dp[0][0][0]=0。然而似乎u的边界不好确定,我们需要保证处理的都是可能出现的情况,所以需要将不可能的情况筛去,观察到每个转移方程的最优解都取决于子问题的最优解dp[i][j][u],因此,我们可以初始化数组 dp 所有元素值为 -1,然后根据初始条件往后拓展,在进行状态转移时,如果遇到的情况时,就直接跳过,因为这说明这种情况不能由初始情况 推导而来。

代码

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <bits/stdc++.h>
#define ll int
#define MAXN 205
using namespace std;

ll dp[MAXN][MAXN][MAXN];

ll answer(char *str, ll n, char *ptr, ll k) {
    ll e01 = ptr[0] == ptr[1];
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;
    for(ll i = 0; i < n; ++i) {
        ll e0 = str[i] == ptr[0];
        ll e1 = str[i] == ptr[1];
        for(ll j = 0; j <= k; ++j) {
            for(ll t = 0; t <= n; ++t) {
                if(dp[i][j][t] == -1)   continue;
                dp[i+1][j][t+e0] = max(dp[i+1][j][t+e0], dp[i][j][t]+(e1?t:0));
                if(j < k) {
                    dp[i+1][j+1][t+1] = max(dp[i+1][j+1][t+1], dp[i][j][t]+(e01?t:0));
                    dp[i+1][j+1][t+e01] = max(dp[i+1][j+1][t+e01], dp[i][j][t]+t);
                }
            }
        }
    }
    ll ans = 0;
    for(ll j = 0; j <= k; ++j) {
        for(ll t = 0; t <= n; ++t) {
            ans = max(ans, dp[n][j][t]);
        }
    }
    return ans;
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    char str[205], ptr[4];
    scanf("%s%s", str, ptr);
    int ans = answer(str, n, ptr, k);
    printf("%d\n", ans);
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-09-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Educational Codeforces Round 81 (Rated for Div. 2)
B. Infinite Prefixes 无限前缀 You are given string ? of length ? consisting of 0-s and 1-s. You build an
ACM算法日常
2020/02/17
3880
Educational Codeforces Round 81 (Rated for Div. 2)
Codeforces Round #624 (Div. 3) C - Perform the Combo
You want to perform the combo on your opponent in one popular fighting game. The combo is the string ss consisting of nn lowercase Latin letters. To perform the combo, you have to press all buttons in the order they appear in ss. I.e. if s=s="abca" then you have to press 'a', then 'b', 'c' and 'a' again.
glm233
2020/09/28
6750
Codeforces Round #625 (Div. 2, based on Technocup 2020 Final Round) C. Remove Adjacent
You are given a string ss consisting of lowercase Latin letters. Let the length of ss be |s||s|. You may perform several operations on this string.
glm233
2020/09/28
5210
AIM Tech Round 4 (Div. 2)(A,暴力,B,组合数,C,STL+排序)
A. Diversity time limit per test:1 second memory limit per test:256 megabytes input:standard input output:standard output Calculate the minimum number of characters you need to change in the string s, so that it contains at least k different letters, or pr
Angel_Kitty
2018/04/09
6920
AIM Tech Round 4 (Div. 2)(A,暴力,B,组合数,C,STL+排序)
CodeForces 832B Petya and Exam
B. Petya and Exam time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output It's hard times now. Today Petya needs to score 100 points on Informatics exam. The tasks seem easy to Petya, but h
ShenduCC
2018/04/27
6620
CodeForces - 999C Alphabetic Removals
 consisting of   lowercase Latin letters. Polycarp wants to remove exactly   characters ( ) from the string  . Polycarp uses the following algorithm   times:
Lokinli
2023/03/09
3020
Codeforces Round #547 (Div. 3)D. Colored Boots
D. Colored Boots time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output There are nn left boots and nn right boots. Each boot has a color which is denoted as a lowercase Latin letter or a question mark
glm233
2020/09/28
4050
1143. Longest Common Subsequence
Given two strings text1 and text2, return *the length of their longest common subsequence. *If there is no common subsequence, return 0.
ppxai
2023/11/18
1800
Codeforces Round #410 (Div. 2)(A,字符串,水坑,B,暴力枚举,C,思维题,D,区间贪心)
A. Mike and palindrome time limit per test:2 seconds memory limit per test:256 megabytes input:standard input output:standard output Mike has a string s consisting of only lowercase English letters. He wants to change exactly one character from the string
Angel_Kitty
2018/04/08
1.1K0
Codeforces Round #410 (Div. 2)(A,字符串,水坑,B,暴力枚举,C,思维题,D,区间贪心)
Codeforces Round #409 (rated, Div. 2, based on VK Cup 2017 Round 2)(A.思维题,B.思维题)
A. Vicious Keyboard time limit per test:2 seconds memory limit per test:256 megabytes input:standard input output:standard output Tonio has a keyboard with only two letters, "V" and "K". One day, he has typed out a string s with only these two letters. He
Angel_Kitty
2018/04/08
7700
字符串基础题
总结:所有题目都已做,有些Easy没有做第二遍,有两道没有accept,请戳 link-en, link-cn
王脸小
2019/11/02
9900
2018四川省大学程序设计竞赛(ACM)B: Beyond the Boundry ----------C语言——菜鸟级
B: Beyond the Boundry Time Limit: 1000 MS Memory Limit: 1048576 KB Total Submit: 98 Accepted: 51 Page View: 407 Submit Status Clarify
Fivecc
2022/11/21
1890
CodeForces 156A Message(暴力)
A. Message time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Dr. Moriarty is about to send a message to Sherlock Holmes. He has a string s. String p is called a substring of string s
ShenduCC
2018/04/26
8100
792. Number of Matching Subsequences
思路: 从note中可以看出words的长度不长,而S的长度最大有50000,暴力的做法:每个word去匹配S,因为S没有记忆成高效数据结构,每次匹配都会重新遍历一次S,时间复杂度为O(len(S)),显然会超时。
用户1147447
2019/05/26
4570
【题解】Gym – 102307C Common Subsequence
题目大意就是给出两个序列,找他们的最长公共子序列,然后判断这个子序列的长度是否大于原序列的0.99。
灯珑LoGin
2022/10/31
1670
求多个子串$\{s_1,...,s_n\}$的序列组合问题.
用户1175855
2024/01/19
1350
hdu----(5056)Boring count(贪心)
Boring count Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 228    Accepted Submission(s): 90 Problem Description You are given a string S consisting of lowercase letters, and your task is coun
Gxjun
2018/03/26
7670
程序员进阶之算法练习(三十九)Codeforces
正文 1.Drinks Choosing 题目链接 题目大意: 有n个学生,每个学生都有自己喜欢的饮料类型,用整数?1,?2,…,?? (1≤??≤?)表示,一共有k种饮料的类型。 现在老师要采
落影
2020/04/09
4760
UVA12467「Secret Word」
Alicia and Roberto like to play games. Today, Roberto is trying to guess a secret word that Alicia chose. Alicia wrote a long string in a piece of paper and gave Roberto the following clues:
hotarugali
2022/03/02
7590
Codeforces 626F Group Projects(滚动数组+差分dp)
F. Group Projects time limit per test:2 seconds memory limit per test:256 megabytes input:standard input output:standard output There are n students in a class working on group projects. The students will divide into groups (some students may be in groups
Angel_Kitty
2018/04/09
7530
Codeforces 626F Group Projects(滚动数组+差分dp)
相关推荐
Educational Codeforces Round 81 (Rated for Div. 2)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档