文章 47
评论 4
浏览 11472
关于动态规划的一点小想法

关于动态规划的一点小想法

最近一直在做动态规划的题,也算有了一些自己的小感悟,暂时总结一下 首先看一道例题 题目链接 描述 X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。 地宫的入口在左上角,出口在右下角。 小明被带到地宫的入口,国王要求他只能向右或向下行走。 走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。 当小明走到出口时,如果他手中的宝贝恰好是 k 件,则这些宝贝就可以送给小明。 请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k 件宝贝。 输入 输入一行 3 个整数,用空格分开:n m k (1<=n,m<=50, 1<=k<=12) 接下来有 n 行数据,每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值 输出 要求输出一个整数,表示正好取 k 个宝贝的行动方案数。该数字可能很大,输出它对 1000000007 取模的结果。 输入样例1 2 2 2 1 2 2 1 输出样例1 2 输入样例2 2 3....

编译原理笔记(6)

编译原理笔记(6)

编译原理笔记——语义分析

编译原理笔记(5)

编译原理笔记(5)

编译原理第五章笔记

编译原理笔记(4)

编译原理笔记(4)

编译原理第四章笔记

谱聚类再次整理

谱聚类再次整理

常读常新啊,又更新一次,理解又加深一次!

编译原理笔记(3)

编译原理笔记(3)

编译原理第三章笔记

最小生成树算法

最小生成树算法

引入问题 首先来看这样一个问题 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数 N(≤1000)和候选道路数目 M(≤3N);随后的 M 行对应 M 条道路,每行给出 3 个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从 1 到 N 编号。 输出格式: 输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出 −1,表示需要建设更多公路。 根据题目的描述,我们可以得知这是一道图论的题目,图为带权无向图,边上的权值即为题中描述的道路修建成本。 现在需要我们根据已有的图,求该图的最小(权值和最小)生成树。 这时候就需要引入解决问题的最小生成树算法了。 Prim 算法思路 首先读入所有的边,边的数据结构是一个结构体,主要包括:起点、终点、权值。 读入边之后按照边的权值由小到大排序。初始化一个数组记录边加入生成树的状态,初始时全部边为未加入。再初始化一个数组记录结点加入生成树的情况。 将某一个结点加入生成树(改变状态标志),因为所....

编译原理笔记(2)

编译原理笔记(2)

编译原理第二章笔记

整型数二进制1的个数

整型数二进制1的个数

这是由BBfat推荐给我的一道经典面试题

编译原理笔记(1)

编译原理笔记(1)

编译原理第一章的笔记

闻道