1258：【例9.2】数字金字塔_方法二：记忆化搜索

旧城等待， 2022-01-16 11:35 246阅读 0赞

/  
*1258：【例9.2】数字金字塔\_方法二：记忆化搜索  
[http://ybt.ssoier.cn:8088/problem\_show.php?pid=1258][http_ybt.ssoier.cn_8088_problem_show.php_pid_1258]*  
/  
\#include <iostream>  
\#include <algorithm>  
using namespace std;

const int MAXN = 505;  
int A\[MAXN\]\[MAXN\],F\[MAXN\]\[MAXN\],N;

int Dfs(int x,int y)  
\{  
if (F\[x\]\[y\]==-1)  
\{  
if (x==N)  
\{  
F\[x\]\[y\]=A\[x\]\[y\];  
cout<<"x0="<<x<<" y="<<y<<" "<<F\[x\]\[y\]<<endl;  
\}  
else  
\{  
F\[x\]\[y\]=A\[x\]\[y\]+max(Dfs(x+1,y),Dfs(x+1,y+1));  
cout<<"x1="<<x<<" y="<<y<<" "<<F\[x\]\[y\]<<endl;  
\}  
cout<<"------------------------------"<<endl;

}
    return F[x][y];

\}

int main()  
\{  
freopen("a.in","r",stdin);  
freopen("b.out","w",stdout);

cin >> N;
    for(int i = 1;i <= N;i ++)
    for(int j = 1;j <= i;j ++)
        cin >> A[i][j];
    
    for(int i = 1;i <= N;i ++)      
    for(int j = 1;j <= i;j ++)              
        F[i][j] = -1;   
    
    Dfs(1,1);
    
    cout<<"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"<<endl;
    cout << F[1][1] << endl;
    
    fclose(stdin);
    fclose(stdout);
    
    return 0;

\}  
/  
*由于F\[x\]\[y\]对于每个合法的(x,y)都只计算过一次，  
而且计算是在O(1)内完成的，因此时间复杂度为O(N^2)。  
可以通过本题。*  
/

转载于:https://blog.51cto.com/1443208/2394219

[http_ybt.ssoier.cn_8088_problem_show.php_pid_1258]: http://ybt.ssoier.cn:8088/problem_show.php?pid=1258

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1181（记忆化搜索）

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

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

相关记忆化搜索——滑雪

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

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

相关 ural 1009 记忆化搜索

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

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

相关 Java实现记忆化搜索

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

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

相关 HDU2571(记忆化搜索)

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

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

相关滑雪【记忆化搜索】

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

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

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

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

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

相关 HDU5456 记忆化搜索

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

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

相关 1258：【例9.2】数字金字塔_方法二：记忆化搜索

/ 1258：【例9.2】数字金字塔\_方法二：记忆化搜索 [http://ybt.ssoier.cn:8088/problem\_show.php?pid=1258]

旧城等待，/ 2022年01月16日 11:35/ 0 赞/ 247 阅读

相关 UVALive 6470 Chomp --记忆化搜索

题意：给一个只有三行的方块阵（横向最多100个），然后p,q,r分别代表第1,2,3层的方格数，两人轮流去掉一个格子，此时这个格子的右上方都会被去掉，面临只剩最左下角的一个格子

淩亂°似流年/ 2021年10月24日 01:58/ 0 赞/ 378 阅读