区间动规 - hzwer.com

算法设计与分析讨论班上机作业
凸包A:WallPOJ1113求凸包周长加一个圆[crayon-6a270c0b4c4dc450122744/]B:ScrambledPolygonPOJ2007排序凸包上的点[crayon-6a270c0b4c4e8867688392/]动态规划G题真的坑A:Fourier’sLinesPOJ1923[crayon-6a270c0b4c4ed592452835/]B:TourPOJ2677[crayon-6a270c0b4c4f2951109560/]C:IncreasingSequencesPOJ1239[crayon-6a270c0b4c4f7749123001/]D:Charlie’sChangePOJ1787[crayon-6a270c0b4c4fe213...
02018年4月2日9,446递推与动规,区间动规,凸包

2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-6a270c0b4d847289734406/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-6a270c0b4d852606246703/]D.Factors爆搜前16个素数[crayon-6a270c0b4d85f882555825/]F.LowPower二分答案贪心检验[crayon-6a270c0b4d867255610589/]H:М...
12017年8月9日9,429STL,贪心,区间动规,深度搜索,二分法,最大流,几何,最短路,单调栈,排列组合
CERC 2014 填坑计划(9 / 12)
又是一个深不见底的大坑9/12A.Parades树形dp，dp[x]=∑dp[son]可能还有从一个子树出发，到达另一个子树的路径在每个结点记录在这棵树最优解的情况下去掉覆盖的路径树根能到达的点，这个每次暴力合并每个结点用状压dp配对子树得出最优解[crayon-6a270c0b4e2a5336570002/]C.Sum我傻逼了。。。枚举答案后二分（其实可以直接算）不合法的情况似乎是2的幂[crayon-6a270c0b4e2b3795218480/]D.Wheels模拟[crayon-6a270c0b4e2b864947...
02015年5月16日5,847区间动规,贪心,STL,深度搜索,二分法,树形动规,状压动规
「BZOJ1055」[HAOI2008] 玩具取名
Description某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。Input第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行，每行两个字母,表示W可以用这两...
12014年12月1日6,434区间动规,记忆化搜索
「NOIP模拟赛」秘密文件
「问题描述」某天，情报局得到了一份秘密文件。文件的内容是加密后的全部由大写字母组成字符串。情报局局长小明想将其发送给远在东方神秘的xx大陆上的老朋友小刘来解密。然而若字符串太长，则需要很长的发送时间，太不安全了，因此小明想尽量将其缩短。于是小明制定了这样一个缩短规则：若一个字符串t连续出现k次，则可以用k(t)进行说明。如ABABAB可以缩成3(AB)。当然，重复缩短是允许的，如ABABABAAAAAAARA...
02014年7月10日4,403区间动规
「BZOJ1260」[CQOI2007] 涂色paint
Description假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。用尽量少的涂色次数达到目标。Input输入仅一行，包含一个长度为n的字符串，即涂色目...
02014年5月22日6,381区间动规
「BZOJ1090」[SCOI2003] 字符串折叠
Description折叠的定义如下：1.一个字符串可以看成它自身的折叠。记作SS2.X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)SSSS…S(X个S)。3.如果AA’,BB’，则ABA’B’例如，因为3(A)=AAA,2(B)=BB，所以3(A)C2(B)AAACBB，而2(3(A)C)2(B)AAACAAACBB给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CC...
02014年3月9日6,269区间动规
「BZOJ1068」[SCOI2007] 压缩
Description给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程：另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。Input输入仅一行，包...
22014年3月9日7,753区间动规
「JoyOI1466」最美妙的矩阵
背景BackgroundCandy的生日即将到来，飘飘乎居士希望找到一个最美妙的矩阵送个Candy作为礼物描述Description飘飘乎居士从Pink处得知最美妙的矩阵满足三个条件：首先，它的长和宽都必须和矩阵的边界平行（也就是不可以出现斜的矩阵）；第二：子矩阵横竖都要满足单调递增（可以相等，也就是对于每一个最优子矩阵的元素都要满足a[i][j]>=a[i-1][j] and a[i][j]>=a[i][j-1]，其中a[i][j]表示矩阵第i行第j列的数字）；第三...
02014年3月3日4,285区间动规
NOIP2003加分二叉树
题目描述 Description设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分×subtree的右子树的加分＋subtree的根的分数若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一...
02014年1月14日5,371区间动规
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日7,346区间动规,深度搜索
寻找牧场
来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1290题目描述Farmer John把家安在Y山林里，有一天他外出寻找新的牧场却走迷路了感觉他自己一直在兜圈。他只依稀记得他家附近n*n大小地区的海拔，他还可以观测到附近n*n大小地区的海拔情况。于是他希望通过判断海拔情况判断他家是否在附近。他于是定义两个区域的相似程度是它们最大公共子矩阵的边长。你的任务就是帮忙他算出两个地区的相似程度以帮助他判断下一步应...
02013年12月19日3,707区间动规