UVA1637Double Patience(概率 + 记忆化搜索)
训练指南P327题意：36张牌分成9堆， 每堆4张牌。每次拿走某两堆顶部的牌，但需要点数相同。如果出现多种拿法则等概率的随机拿。 如果最后拿完所有的牌则游戏成功，求成功的概率。开个9维数组表示每一堆的状态，模拟搜索一下 #include <iostream> #include <c...
bzoj 1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富【记忆化搜索+剪枝】
c[x][y]为从(x,y)到(n,m)的最大值，记忆化一下有个剪枝是因为y只能+1所以当n-x>m-y时就算x也一直+1也是走不到(n,m)的，直接返回0即可#include<iostream>#include<cstdio>using namespace std;c...
【蓝桥杯真题】地宫取宝(搜索->记忆化搜索详解)
链接[蓝桥杯][2014年第五届真题]地宫取宝题目描述X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。地宫的入口在左上角，出口在右下角。小明被带到地宫的入口，国王要求他只能向右或向下行走。走过某个格子时，如果那个格子中的宝贝价值比小明手中任意...
loj 1044(dp+记忆化搜索）
题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26764思路：dp[pos]表示0-pos这段字符串最少分割的回文子串，然后记忆化搜索（判断是否是回文子串的时候也用一个数组来记录是否是回文子串，记忆化搜索）。 #in...
DP(记忆化搜索) + AC自动机 LA 4126 Password Suspects
题目传送门题意：训练指南P250分析：DFS记忆化搜索，范围或者说是图是已知的字串构成的自动机图，那么用 | (1 << i)表示包含第i个字串，如果长度为len，且st == (1 << m) - 1则是可能的。打印与之前相似。#include <bits/stdc+...
NYOJ16|嵌套矩形|DP|DAG模型|记忆化搜索
矩形嵌套时间限制：3000 ms | 内存限制：65535 KB难度：4描述有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。例如（1,5）可以嵌套在（6,2）内...
LOJ2803 CCC2018 平衡树 数论分块、记忆化搜索
传送门题意差评，其实就是一个递推式：\(f_1 = 1 , f_i = \sum\limits_{j=2}^i f_{\lfloor \frac{i}{j} \rfloor}\)，然后求\(f_N\)的值首先\(\lfloor \frac{i}{j} \rfloor\)只有\(2\sqrt{i}\)...
poj 1579 Function Run Fun(记忆化搜索+dp)
题目链接：http://poj.org/problem?id=1579思路分析：题目给出递归公式，使用动态规划的记忆搜索即可解决。代码如下:#include <stdio.h>#include <string.h>const int MAX_N = + ;int dp[MA...
UVA 10285 - Longest Run on a Snowboard (记忆化搜索+dp）
Longest Run on a SnowboardInput: standard inputOutput: standard outputTime Limit: 5 secondsMemory Limit: 32 MBMichael likes snowboarding. That's not v...
UVa 10617 Again Palindromes / 记忆化搜索
删除若干个字母后 剩下的是回文串 求有多少个记忆化搜索 dp[i][j]表示i j 之间有多少个 其实递推也可以的 long long#include <stdio.h>#include <string.h>long long dp[70][70];char a[70];lo...
LightOJ1417 Forwarding Emails（强连通分量+缩点+记忆化搜索）
题目大概是，每个人收到信息后会把信息发给他认识的一个人如此下去，问一开始要把信息发送给谁这样看到信息的人数最多。首先找出图中的SCC并记录每个SCC里面的点数，如果传到一个SCC，那么里面的人都可以看到信息。然后SCC缩点后就形成DAG，直接记忆化搜索，d(u)搜索从u点出发开始传最多能传多少人。最...
Codevs_1017_乘积最大_(划分型动态规划/记忆化搜索)
描述http://codevs.cn/problem/1017/给出一个n位数,在数字中间添加k个乘号,使得最终的乘积最大.1017 乘积最大 2000年NOIP全国联赛普及组NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 De...
Educational Codeforces Round 1 E. Chocolate Bar 记忆化搜索
E. Chocolate BarTime Limit: 20 SecMemory Limit: 256 MB题目连接http://codeforces.com/contest/598/problem/EDescriptionYou have a rectangular chocolate bar c...
Codeforces Gym 100231G Voracious Steve 记忆化搜索
Voracious Steve题目连接：http://codeforces.com/gym/100231/attachmentsDescription有两个人在玩一个游戏有一个盆子里面有n个甜甜圈，A先开始，他可以抓[1,min(m,n)]颗甜甜圈，然后B开始，同样，可以抓[1,min(n,m)]个...
单词拆分(字典树、记忆化搜索)、字母异位词分组(哈希表、字符串）、定义一个类Generator(散列表)
单词拆分(字典树、记忆化搜索)给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：输入: s = "leetcode", wordDict = ...
反转链表(递归、链表)、爬楼梯(记忆化搜索、数学)、旋转数组(数组、数学)
反转链表(递归、链表)给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 输入：head = [1,2] 输出：[2,1] 输入：head = [] 输出：[]示例 1：示例 2：示例 3：提示：链表中节点的数目...
练习题 No.5 背包问题(动态规划-记忆化搜索)
要求有n个背包和价值分为 wi , vi 的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。限制条件 (1 <= n <= 100) (1 <= wi , vi <= 100)...
uva 10118，记忆化搜索
这个题debug了长达3个小时，acm我不能放弃，我又回来了的第一题！一开始思路正确，写法不行，结果越改越乱看了网上某神的代码，学习了一下coding+debug：4小时左右，记忆化搜索+dp类型第一题/* * Author: Bingo * Created Time: 2015/3/2 21:...
UVA - 10118 Free Candies(免费糖果)(dp---记忆化搜索)
题意：桌上有4堆糖果，每堆有N(N<=40)颗。佳佳有一个最多可以装5颗糖的小篮子。他每次选择一堆糖果，把最顶上的一颗拿到篮子里。如果篮子里有两颗颜色相同的糖果，佳佳就把它们从篮子里拿出来放到自己的口袋里。如果篮子满了而里面又没有相同颜色的糖果，游戏结束，口袋里的糖果就归他了。问最多能拿到多少...
GYM 100608G 记忆化搜索+概率 2014-2015 Winter Petrozavodsk Camp, Andrew Stankevich Contest 47 (ASC 47)
https://codeforces.com/gym/100608题意:两个人玩游戏,每个人有一个长为d的b进制数字,两个人轮流摇一个$[0,b-1]$的骰子,并将选出的数字填入自己的d个空位之中最后数字大的人赢有两种玩法,第一个是轮流玩,一个是第一个人玩d次之后,第二个人玩两个人都非常聪明,求第一...