Problem #3365 - ECNU Online Judge

zhangjc

4 年，4 月前

请问一下这道题您做出来了吗？我卡在了27个测试用例上：），想请教一下

回复 0 0

CCXXXI_

4 年，4 月前

相信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, '_'))

回复 0 0

zhangjc

4 年，4 月前

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

回复 0 0

CCXXXI_

4 年，4 月前

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

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

回复 0 0

zhangjc

4 年，4 月前

我的dp是有问题！！！！

回复 0 0

zhangjc

4 年，4 月前

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做的

回复 0 0

我收拾一下就滚

7 年前

唉.

回复 0 0

3365. 打字员吉吉木

服务

开源

关于我们