3365. 打字员吉吉木

zhangjc

我的dp是有问题!!!!

zhangjc

struct state{
long num;
string copy;
state(int num, string copy){
this->num = num;
this->copy = copy;
}
state(){
this->num = 0;
this->copy = “”;
}
};
int helper(string s){
if (s.length() <= 3)
return s.length();
int n = s.size();
vector dp(n);
dp[0].num = 1;
dp[1].num = 2;
//dp[i]表示0-i打印出来需要的最短时间
for (int i = 2; i <n; i++){
//遍历前面
dp[i].num = dp[i - 1].num + 1; //默认直接输出一个字符
//j表示从i开始往前数j个是通过粘贴来的
for (int j = 2; j <= (i + 1) / 2; j++){
if (dp[i - j].copy == s.substr(i - j + 1, j)){
if (dp[i].num >= dp[i - j].num + 1){
dp[i].num = dp[i - j].num + 1;
dp[i].copy = dp[i - j].copy;
}
}

        if (match(s.substr(0, i - j + 1), s.substr(i - j + 1, j))){
            if (dp[i].num >= dp[i - j].num + 2){
                dp[i].num = dp[i - j].num + 2;
                dp[i].copy = s.substr(i - j + 1, j);
            }
        }

    }
}
return dp[n - 1].num;

}
用dp做的

我收拾一下就滚

唉.

zhangjc

请问一下这道题您做出来了吗?我卡在了27个测试用例上:),想请教一下

CCXXXI_

相信eoj的速度,直接暴搜就行了,超时就加个记忆化,仍然超时就多交几次试试


from functools import lru_cache

s = input()


@lru_cache(None)
def dfs(idx: int, cp: str):
    if idx == len(s):
        return 0
    a_tm = dfs(idx + 1, cp) + 1
    if idx + 1 == len(s) or s[idx:idx + 2] not in s[:idx]:
        return a_tm
    p_tm = dfs(idx + len(cp), cp) + 1 if s[idx:idx + len(cp)] == cp else 10032
    ed = idx + 2
    while ed != len(s) and s[idx:ed + 1] in s[:idx]:
        ed += 1
    cp_tm = min(dfs(i, s[idx:i]) for i in range(idx + 2, ed + 1)) + 2
    return min(a_tm, p_tm, cp_tm)


print(dfs(0, '_'))
zhangjc

这样的dfs思路真的太棒了,受教了受教了,我是用dp做的,依次检查前面的,不知道哪里错了一直卡在第27个测试用例上,不过,我把您的这个方法改成C++后发现需要加记忆化,否则还是过不了,太感谢了

CCXXXI_

可以加上记忆化先AC一次,然后就可以看其他人曾经交过的代码了(在统计数据中)

另外发代码需要加上特定标记才能保留缩进,具体语法在这里

你当前正在回复 博客/题目
存在问题!