动态规划 - Page 27

「CODEVS1403」新三国争霸
题目描述 DescriptionPP特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。在这款游戏中，加入灾害对道路的影响（也就是一旦道路W[i，j]受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路W[i，j]，至少需要K[i，j]个士兵才能守住）。PP可真是高手，不一会，...
02014年2月5日3,714递推与动规,kruskal

无聊写的A+B问题。。。
输入A,B输出A+B[crayon-6743538c567d9503926391/]
42014年2月3日8,993spfa,kruskal,最小割,背包动规,floyd,线段树,树状数组
「CODEVS2800」送外卖
题目描述 Description有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），最后还要回到0点（他的单位），请问最短时间是多少。现在已知任意两个城市的直接通路的时间。输入描述 InputDescription第一行一个正整数n（1<=n<=15）接下来是一个（n+1）*(n+1)的矩阵，矩阵中的数均...
02014年2月1日4,040深度搜索,floyd,状压动规
「CODEVS1050」棋盘染色 2
题目描述 Description有一个5*N的棋盘，棋盘中的一些格子已经被染成了黑色，你的任务是对最少的格子染色，使得所有的黑色能连成一块。输入描述 InputDescription第一行一个整数N(<=100)，接下来N行每行一个长度为5的01串，1表示所在格子已经被染成了黑色，0表示所在格子没有被染色。输出描述 OutputDescription第一行一个整数N(<=100)，接下来N行每行一个长度为5的01串，1表示所在格子已经被染成了黑色，0表示所...
32014年1月31日4,779迭代深搜,状压动规
「BZOJ1087」[SCOI2005] 互不侵犯King
Description在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。Input只有一行，包含两个数N，K（1<=N<=9,0<=K<=N*N）Output方案数。SampleInput32SampleOutput16代码[crayon-6743538c57acc912172915/] ...
02014年1月27日7,589状压动规
「JoyOI1087」sumsets
题目描述正整数N可以被表示成若干2的幂次之和。例如，N = 7时，共有下列6种不同的方案：1) 1+1+1+1+1+1+12) 1+1+1+1+1+23) 1+1+1+2+24) 1+1+1+45) 1+2+2+26) 1+2+4 给出正整数N，计算不同方案的数量（保留最后9位数字）。输入一个整数，表示正整数N。输出一个整数，表示不同方案的数量。样例输入7样例输出6提示 1 <= N <= 1000000 代码[crayon-6743538c57e40895615177/] ...
02014年1月23日2,786背包动规
「JoyOI1089」smrtfun
题目描述现有N个物品，第i个物品有两个属性A_i和B_i。在其中选取若干个物品，使得sum{A_i + B_i}最大，同时sum{A_i}，sum{B_i}均非负（sum{}表示求和）。输入第一行，一个整数，表示物品个数N。接下来N行，每行两个整数，表示A_i和B_i。输出一个整数，表示最大的sum{A_i + B_i}。样例输入5-578-66-321-8-5样例输出8提示 N <= 100 , |A_i| <= 1000 , |B_i| <= 1000代码[...
02014年1月23日2,940背包动规
「JoyOI1096」数字组合
题目描述在N个数中找出其和为M的若干个数。先读入正整数N（1<N<100）和M(1<M<10000)，再读入N个正数（可以有相同的数字，每个数字均在1000以内），在这N个数中找出若干个数，使它们的和是M，把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。要求你的程序运行时间不超过1秒。输入第一行是两个数字，表示N和M。第二行起是N个数。输出就一个数字，表示和为M的...
02014年1月23日3,115递推与动规,深度搜索
「BZOJ1084」[SCOI2005] 最大子矩阵
Description这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。Input第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。Output只有一行为k个子矩阵分值之和最大为多少。SampleInput3221-323-23SampleOutput9题解[crayon-6743538c58885379417731/] ...
22014年1月15日7,698递推与动规
NOIP2003加分二叉树
题目描述 Description设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分×subtree的右子树的加分＋subtree的根的分数若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一...
02014年1月14日4,933区间动规
NOIP2002矩形覆盖
题目描述 Description在平面上有n个点（n<=50），每个点用一对整数坐标表示。例如：当n＝4时，4个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7）这些点可以用k个矩形（1<=k<4）全部覆盖，矩形的边平行于坐标轴。当k=2时，可用如图二的两个矩形sl，s2覆盖，s1，s2面积和为4。问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为0；覆盖平...
22014年1月13日6,505区间动规,深度搜索
「vijos1055」奶牛浴场
描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮...
12014年1月6日4,047递推与动规