POJ 3616 DP
poj2411 Mondriaan's Dream 状压DP
Mondriaan's Dream Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 22073 Accepted: 12368 Description Squares and rectangles fascinated the famous
日期 2023-06-12 10:48:40
HDU 1400 （POJ 2411 ZOJ 1100）Mondriaan's Dream（DP + 状态压缩）
Mondriaan's Dream Problem Description Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use hi
日期 2023-06-12 10:48:40
poj 3311 状压DP
经典TSP变形 学到：1、floyd O(n^3)处理随意两点的最短路 2、集合的位表示,我会在最后的总结出写出。注意写代码之前一定设计好位的状态。本题中，第0位到第n位分别代表第i个城市，1是已经走过，0没走过 那么DP方程 ：dp[s][i]--当前在城市i。状态为s(s存储的是走过了那些城市) &n
日期 2023-06-12 10:48:40
poj 1160 Post Office (间隔DP)
Post Office Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 15966 Accepted: 8671 Description There is a straight highway with villages alo
日期 2023-06-12 10:48:40POJ 3280 间隔DP
字符串，每次插入或删除字符需要一定的价格，问：我怎样才能使这个字符串转换成字符串回文，花最少。 间隔DP 当DP到区间[i,j+1]时，我们能够在i-1的位置加入一个str[j+1]字符，或者将在j+1处的字符删除。得到一个新的回文串，并且我们这两步操作都没有借助或者影响区间[i,j]的情况。 因此，那我们就能够将加入或者删除整合在一起，对字符str[j+1]的操作就依照加入和删除中花
日期 2023-06-12 10:48:40
POJ 1458-Common Subsequence（线性dp/LCS）
Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 39009 Accepted: 15713 Description A subsequence of a given sequence is th
日期 2023-06-12 10:48:40POJ3254 Corn Fields 状态压缩DP
看了这位博主的经历 http://blog.csdn.net/lenleaves/article/details/7972224 感觉有些差点儿相同，由于CF比赛状压被虐 所以開始刷刷题，从最简单的開始复习吧，细节处理非常差。唉 DP方程跟一般的有些不一样。dp[i][j]表示在状态i的情况下 到第j行的摆放有多少种，然后总数就是 dp[i][n - 1]求和，以第一行为边界往下推。第一
日期 2023-06-12 10:48:40POJ 2151 Check the difficulty of problems （动态规划-可能DP）
Check the difficulty of problems Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 4522 Accepted: 1993 Description Organizing a programming
日期 2023-06-12 10:48:40poj3671Dining Cows(DP)
主题链接： 啊哈哈，点我点我 题意： 给一个仅仅含有1。2的序列，如何变换n次使序列成为一个非递减的序列，而且使n最小。 思路： 这道题的数据范围是50000，则肯定承受不了n方的复杂度。所以 仅仅能写O(n)的算法，甚至更小，所以当时想二分，可是不知道怎么写，忽然想到能够枚举每个位置，把每个位置都当做一个分界点。然后求前半部有多少个2。后半段有多少个1，最后和所有是1和2进行比較，这个问
日期 2023-06-12 10:48:40POJ 3691 DNA repair 基于AC自己主动机DP
dp[i][j] 它表示的长度 i 下游前缀 j 更改节点的最小数量。 很清楚dp[0][0] = 0; dp[ i ][ j ] = min(dp[ i ][ j ],dp[i-1][k] + (j == k ? 0 : 1)),当且仅当j。k满足下列条件时。 j 不为某条模式串的末节点 且 j 到 root 的由失败指针组成的路径上无末节点。 j 是k的儿子节点 或者 j 的父节点可由
日期 2023-06-12 10:48:40POJ3080方法很多（暴力，KMP,后缀数组，DP）
题意： 给n个串（n>=2&&n<=10），每个串长度都是60，然后问所有串的最长公共子串，如果答案不唯一输出字典序最小的。 思路：直接暴力，枚举+KMP，后缀数组 枚举+KMP #include<stdio.h> #in
日期 2023-06-12 10:48:40POJ3080方法很多（暴力，KMP,后缀数组，DP）
题意： 给n个串（n>=2&&n<=10），每个串长度都是60，然后问所有串的最长公共子串，如果答案不唯一输出字典序最小的。 思路：直接暴力，枚举+KMP，后缀数组 枚举+KMP #include<stdio.h> #in
日期 2023-06-12 10:48:40poj1837--Balance(dp：天平问题)
Balance Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 10773 Accepted: 6685 Description Gigel has a strange "balance" and he wants to poise i
日期 2023-06-12 10:48:40POJ 2778 DNA Sequence (AC自动机+DP+矩阵)
题意：给定一些串，然后让你构造出一个长度为 m 的串，并且不包含以上串，问你有多少个。 析：很明显，如果 m 小的话 ，直接可以用DP来解决，但是 m 太大了，我们可以认为是在AC自动机图中，根据离散中的矩阵的幂可以表示 从 i 到 j 需要 x 步的有多少条。比如A[1][2]^5 = 10，表示从结点 1 到结点 2 走五步有10种方法，利用这种方法，就可以直接进行矩阵快速幂了。 代码如下：
日期 2023-06-12 10:48:40
POJ 2152 Fire (树形DP)
题意：给定一棵树，要建立一些消防站，并且每个结点到最近一个的消防站的距离不能超过limit i，在每个结点建立消防站要花一定的费用cost i，求最少的花费是多少。 析：想了很久，确实是没想出来怎么做，dp[i][j] 表示 i 结点依赖 j 结点的最小花费，然后ans[i] 表示 以 i 为根结点的树，最少花费。在转移时，就是直接枚举 i 结点，所以依赖的 j 结点，然后ans 是取最小值，d
日期 2023-06-12 10:48:40POJ 1185 炮兵阵地 (状压DP)
题意：中文题。 析：dp[i][s][t] 表示第 i 行状态为 s， 第 i-1 行为 t，然后就很简单了，但是要超内存，实际上状态最多才60个，所以后两维开60就好， 然后又超时间，就一直加优化，提前预处理。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #incl
日期 2023-06-12 10:48:40POJ 3691 DNA repair (DP+字符串)
题意：给出nn(1≤n≤50，1≤n≤50) 个病毒DNA序列，长度均不超过20。现在给出一个长度不超过1000的字符串，求至少要更换多少个字符， 才能使这个字符串不包含这些DNA序列。 析：利用前缀来做好状态转移。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #in
日期 2023-06-12 10:48:40POJ 3071 Football (概率DP)
题意：给定 2的n次方 个团队对每个队的战胜的概率，一块要打 n 场，每场都是 1 对 2， 2 对 3，每次都取赢的一方，问你最后谁是冠军的概率最大。 析：dp[i][j] 表示 第 i 场 j 胜的概率，每次只要算 i 相邻的且不是已经打过的 2 i-1次方个队，最后再选出概率最大的就好。 代码如下： #pragma comment(linker, "/STACK:1024000000,1
日期 2023-06-12 10:48:40POJ 1141 Brackets Sequence (区间DP)
题意：给定一个括号序列，让你添加最少的括号，使得所有的括号都匹配。 析：首先用DP来把这个最少的找出来，然后再打印出解，dp[i][j]表示从 i 到 j 所要添加最少的数。 注意有空行的数据。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <s
日期 2023-06-12 10:48:40POJ 3670 Eating Together (DP，LIS)
题意：给定 n 个数，让你修改最少的数，使得它变成一个不下降或者不上升序列。 析：这个就是一个LIS，但是当时并没有看出来。。。只要求出最长LIS的长度，用总数减去就是答案。 代码如下： #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include
日期 2023-06-12 10:48:40POJ 3744 Scout YYF I (概率DP+矩阵快速幂)
题意：小明要从1走过一段直线雷区，给定n个地雷的坐标，他走一步的概率是p，两步的概率为1-p，问你他能安全通过雷区的概率。 析：很明显这是一个概率DP，用d（i）表示到达 i 时他安全的概率，那么d[i] = p * d[i-1] + (1-p) * d[i-2];这个状态转移方程很好理解， 就是说要想到达 i 要么从第 i-1 走一步，要么从 i-2 走两步，最后加起来，然后问题来了，这个数可
日期 2023-06-12 10:48:40【POJ 1112】Team Them Up!（二分图染色+DP）
Description Your task is to divide a number of persons into two teams, in such a way, that: everyone belongs to one of the teams; every team has at least one member; every person in th
日期 2023-06-12 10:48:40POJ1505:Copying Books(区间DP)
Description Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book a
日期 2023-06-12 10:48:40POJ 3592 Instantaneous Transference（强连通+DP）
POJ 3592 Instantaneous Transference 题目链接 题意：一个图。能往右和下走，然后有*能够传送到一个位置。'#'不能走。走过一个点能够获得该点上面的数字值，问最大能获得多少 思路：因为有环先强连通缩点。然后问题转化为dag，直接dp就可以 代码： #include <cstdio> #include <cstring> #i
日期 2023-06-12 10:48:40POJ 1159 Palindrome(区间DP/最长公共子序列+滚动数组)
Palindrome Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 56150 Accepted: 19398 Description A palindrome is a symmetrical string, that is
日期 2023-06-12 10:48:40POJ 1088: 滑雪（经典 DP+记忆化搜索）
滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 74996 Accepted: 27818 Description Michael喜欢滑雪百这并不奇怪， 由于滑雪的确非常刺激。但是为了获得速度，滑的区域必须向下倾斜，并且当
日期 2023-06-12 10:48:40POJ 1260-Pearls（DP）
Pearls Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 7465 Accepted: 3695 Description In Pearlania everybody is fond of pearls. One company
日期 2023-06-12 10:48:40poj 2068 Nim（博弈dp）
Nim Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1403 Accepted: 791 Description Let's play a traditional game Nim. You and I are seat
日期 2023-06-12 10:48:40poj1161Post Office【经典dp】
题目：poj1161Post Office点击打开链接 题意：给出一条直线上的n个坐标表示村庄的位置，然后要在上面建p个邮局。村民优先选择去近的邮局。问全部村庄去邮局的最小距离和是多少？ 分类：区间dp 分析：对于随意一个村庄，仅仅有两种选择，要么在这儿建邮局。要么不建，我们能够预处理出来随意两件建立一个邮局的的最小距离w【i】【j】，而对于随意两点，建立一个邮局的最优方案是建立
日期 2023-06-12 10:48:40POJ 2486 树形DP
有一颗苹果树，每一个节点上面有非常多苹果，从一个节点到另外一个能够到达的节点花费1步。求k步最多能吃到多少苹果，起始点为1，能够不回到起始点。 这是典型的回溯型树状dp。 dp[i][j][0]代表以i为根节点的子树最多j步后回到i能吃到的最多的苹果， dp[i][j][1]代表以i为根节点的子树最多j步后不回到i节点最多能吃到的子树。那么状态转移就分三步了。 （1）dp[i][j
日期 2023-06-12 10:48:40POJ3280 Cheapest Palindrome 【DP】
Cheapest Palindrome Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 6013 Accepted: 2933 Description Keeping track of all the cows can be a
日期 2023-06-12 10:48:40