acm.hdu.edu.cn/showproblem.php?pid=2159 题意：现在玩游戏欲升级，升级需要经验值n，杀怪可以赚经验值，但是会扣忍耐度，游戏中有k种怪，数目都无限多。现在玩家还有m点忍耐度，问能否在最多杀s个怪的情况下升级，若能则输出剩余的最大忍耐度。 思路： 1、此题有两个约束，一个是忍耐度，一个是最多杀的怪物数。抽象来说意味着对于每件物品，具有两种不同的费用。此即为二维背包的模型！而二维费用背包模型最常见的形式便是：物品总个数有上限限制，如此题的最多杀s个怪。而关于二维背包的处理，无非是增加一个状态维度即可，转移方程类比着选或不选第i个物品的思路写出即可。 2、...

地址 poj.org/problem?id=3723 最大生成树 更新一个板子 题意：征用所有人需要(n+m)*10000元。男孩与女孩之间有联系的，征兵所需费用 -d元 #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <map> #include <queue> #include <set> using namespace std;...

地址 poj.org/problem?id=3723 最大生成树 更新一个板子 题意：征用所有人需要(n+m)*10000元。男孩与女孩之间有联系的，征兵所需费用 -d元 #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <map> #include <queue> #include <set> using namespace std;...

感想 入门即劝退 还有个动态主席树先弃坑了 这里贴点其他博客的关键字和解释 主席树的每个节点对应一颗线段树，此处有点抽象。在我们的印象中，每个线段树的节点维护的树左右子树下标以及当前节点对应区间的信息（信息视具体问题定）。对于一个待处理的序列a[1]、a[2]…a[n]，有n个前缀。每个前缀可以看做一棵线段树，共有n棵线段树；若不采用可持久化结构，带来的严重后果就是会MLE，即对内存来说很难承受。根据可持久化数据结构的定义，由于相邻线段树即前缀的公共部分很多，可以充分利用，达到优化目的，同时每棵线段树还是保留所有的叶节点只是较之前共用了很多共用节点。主席树很重要的操作就是如何寻找公用的节点...

感想 入门即劝退 还有个动态主席树先弃坑了 这里贴点其他博客的关键字和解释 主席树的每个节点对应一颗线段树，此处有点抽象。在我们的印象中，每个线段树的节点维护的树左右子树下标以及当前节点对应区间的信息（信息视具体问题定）。对于一个待处理的序列a[1]、a[2]…a[n]，有n个前缀。每个前缀可以看做一棵线段树，共有n棵线段树；若不采用可持久化结构，带来的严重后果就是会MLE，即对内存来说很难承受。根据可持久化数据结构的定义，由于相邻线段树即前缀的公共部分很多，可以充分利用，达到优化目的，同时每棵线段树还是保留所有的叶节点只是较之前共用了很多共用节点。主席树很重要的操作就是如何寻找公用的节点...

题目链接： http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1832 题意： 有n个数字排成一条直线，然后有两个小伙伴来玩游戏， 每个小伙伴每次可以从两端（左或右）中的任意一端取走一个或若干个数（获得价值为取走数之和）， 但是他取走的方式一定要让他在游戏结束时价值尽量的高，最头疼的是两个小伙伴都很聪明，所以每一轮两人都将按照对自己最有利的方法去取数字，请你算一下在游戏结束时，先取数的人价值与后取数人价值之差（不要求绝对值）。...

题目链接： http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1832 题意： 有n个数字排成一条直线，然后有两个小伙伴来玩游戏， 每个小伙伴每次可以从两端（左或右）中的任意一端取走一个或若干个数（获得价值为取走数之和）， 但是他取走的方式一定要让他在游戏结束时价值尽量的高，最头疼的是两个小伙伴都很聪明，所以每一轮两人都将按照对自己最有利的方法去取数字，请你算一下在游戏结束时，先取数的人价值与后取数人价值之差（不要求绝对值）。...

链接：https://www.nowcoder.com/acm/contest/190/G 来源：牛客网 CLS 分苹果 orz 我好菜啊 dp数组大小 一直开的205 orz 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 CSL手上有n个苹果，第i个苹果的质量是wi，现在他想把这些苹果分给他的好朋友wavator和tokitsukaze。但是CSL为了不让他们打架，根据质量决定尽量地均分成两堆分给他们。现在CSL想知道到底给每个人分多少质量的苹果。 注意：苹果不能劈开来...

链接：https://www.nowcoder.com/acm/contest/190/G 来源：牛客网 CLS 分苹果 orz 我好菜啊 dp数组大小 一直开的205 orz 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 CSL手上有n个苹果，第i个苹果的质量是wi，现在他想把这些苹果分给他的好朋友wavator和tokitsukaze。但是CSL为了不让他们打架，根据质量决定尽量地均分成两堆分给他们。现在CSL想知道到底给每个人分多少质量的苹果。 注意：苹果不能劈开来...

B ***游戏 链接：https://www.nowcoder.com/acm/contest/190/B 来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 Alice和Bob产生了不可调节的矛盾，于是他们相约一起玩一个***游戏，输的人就会从这个世界上消失。 游戏开始时，Alice手上拿着一个定时炸弹，炸弹有个倒计时t。炸弹在t=0时刻会爆炸，此时手上拿着炸弹的人会从这个世界上消失。为了增加游戏乐趣，他们约定每个人拿到炸弹后可以选择将炸弹的时间调快d秒(d ∈ [a,...

B 自杀游戏 链接：https://www.nowcoder.com/acm/contest/190/B 来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 Alice和Bob产生了不可调节的矛盾，于是他们相约一起玩一个自杀游戏，输的人就会从这个世界上消失。 游戏开始时，Alice手上拿着一个定时炸弹，炸弹有个倒计时t。炸弹在t=0时刻会爆炸，此时手上拿着炸弹的人会从这个世界上消失。为了增加游戏乐趣，他们约定每个人拿到炸弹后可以选择将炸弹的时间调快d秒(d ∈ [a,b]...

区间DP 算是裸板吧 这次求的是最小值 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5115; 题目大意：总共有N只狼排成一排，每只狼都有一个基础攻击力ai，以及被击杀后可给别的狼提供的攻击力bi（一只狼被攻击的话，它相邻的狼会为它提供额外的攻击力bi），你击杀一只狼都会减少与这只狼攻击力加上相邻的狼提供的额外的攻击力的和的生命值，问如果要将全部狼都击杀，你最少需要减少多少生命值。 枚举区间长度与起点，求出终点，然后枚举起点与终点之间的点。dp[i][j]为杀死i到j的狼所受到的伤害，然后枚举k作为最后一只被杀死的狼，此时受到的伤害为...

区间DP 算是裸板吧 这次求的是最小值 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5115; 题目大意：总共有N只狼排成一排，每只狼都有一个基础攻击力ai，以及被击杀后可给别的狼提供的攻击力bi（一只狼被攻击的话，它相邻的狼会为它提供额外的攻击力bi），你击杀一只狼都会减少与这只狼攻击力加上相邻的狼提供的额外的攻击力的和的生命值，问如果要将全部狼都击杀，你最少需要减少多少生命值。 枚举区间长度与起点，求出终点，然后枚举起点与终点之间的点。dp[i][j]为杀死i到j的狼所受到的伤害，然后枚举k作为最后一只被杀死的狼，此时受到的伤害为...

Matt is a big fan of logo design. Recently he falls in love with logo made up by rings. The following figures are some famous examples you may know. A ring is a 2-D figure bounded by two circles sharing the common center. The radius for these circles are denoted by r and R (r < R). For more det...