Gym - 101889E 记忆化搜索

青旅半醒 2022-05-09 06:50 140阅读 0赞

思维还是太将江华，开始一直想dp，就是这一位余数固定时取最小的一个字符串，但是字符串太大，赋值的时候超时，其实根本没必要存字符串，只要记忆化搜索，看看\[pos\]\[res\]这个状态是否能构成就行，这样的话1000\*1000个状态， 稳稳的，然后贪心从小枚举，第一个可行的一定是最优解。

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e3+10;
    char s[N], ans[N];
    int k, n;
    int dp[N][N];
    
    int dfs(int pos, int res){
        if(pos==n)    return res==0;
        int& ret=dp[pos][res];
        if(ret!=-1) return ret;
    
        if(s[pos]=='?'){
            for(int i=0; i<10; i++){
                if(!pos&&!i) continue;
                ans[pos]=i+'0';
                ret=dfs(pos+1, (res*10+i)%k);
                if(ret==1) return ret;
            }
        }
        else{
            ans[pos]=s[pos];
            ret=dfs(pos+1, (res*10+s[pos]-'0')%k);
        }
        return ret;
    }
    
    int main(){
        scanf("%s", s);
        scanf("%d", &k);
        n=strlen(s);
        memset(dp, -1, sizeof dp);
    
        if(dfs(0,0)==1){
            ans[n]=0;
            for(int i=0; i<n; i++)
                putchar(ans[i]);
            puts("");
        }
        else
            puts("*");
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1181（记忆化搜索）

呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒

我不是女神ヾ/ 2024年02月17日 19:43/ 0 赞/ 75 阅读

相关记忆化搜索——滑雪

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 87592 Accepted: 32835 Des

女爷i/ 2022年08月21日 01:20/ 0 赞/ 204 阅读

相关 ural 1009 记忆化搜索

1009. K-based Numbers Time limit: 1.0 second Memory limit: 64 MB Let’s con

向右看齐/ 2022年08月09日 14:51/ 0 赞/ 181 阅读

相关 Java实现记忆化搜索

记忆化搜索是在使用递归搜索或者类似的情况下使用一般的递归或许需要太多的时间与内存这时我们就可以使用记忆化搜索其本质为在递归搜索中如果遇到了没有搜索过

曾经终败给现在/ 2022年06月01日 13:49/ 0 赞/ 246 阅读

相关 HDU2571(记忆化搜索)

<table style="font-family:'Times New Roman';"> <tbody> <tr> <td align="center">

绝地灬酷狼/ 2022年05月29日 00:15/ 0 赞/ 181 阅读

相关滑雪【记忆化搜索】

滑雪 Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Mich

分手后的思念是犯贱/ 2022年05月25日 04:22/ 0 赞/ 209 阅读

相关滑雪 ————记忆化搜索

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道

￡神魔★判官ぃ/ 2022年05月17日 11:37/ 0 赞/ 171 阅读

相关 HDU5456 记忆化搜索

[传送门][Link 1] 题意：给你n个火柴，能拼成几个A-B=C的等式思路：可以转换位B+C=A，这个题不允许有前导零，0这个数也是不行的，我们从个位开始同时对B,

布满荆棘的人生/ 2022年05月14日 01:38/ 0 赞/ 249 阅读

相关 Gym - 101889E 记忆化搜索

思维还是太将江华，开始一直想dp，就是这一位余数固定时取最小的一个字符串，但是字符串太大，赋值的时候超时，其实根本没必要存字符串，只要记忆化搜索，看看\[pos\]\[res\

青旅半醒/ 2022年05月09日 06:50/ 0 赞/ 141 阅读

相关 gym101915e

include <bits/stdc++.h> define N 10 using namespace std; int a

快来打我*/ 2022年04月24日 11:16/ 0 赞/ 114 阅读