111qqz的小窝

老年咸鱼冲锋!

hdu 2018 母牛的故事 (基础dp,记忆化搜索)

hdu2018题目链接 题意:第1年有1头奶牛,每年生一头奶牛,新生的奶牛从生下来的第四年(包括生下来那年)也开始每年一头奶牛。 问第n年有多少

hdu 2084 数塔 (基础dp)

hdu2084题目链接 题意:dp入门题。。。数字三角形。。 思路: 昨天看mit公开课。。。讲到dp的精髓是sub-problem+ reuse… 为什么自底

hdu 4283 You Are the One (区间dp)

hdu 4283题目链接 题意:有N个人按顺序排成一排上台表演,每个都有一个num[]值,若在他是第k个上场的人,则会有num[]*(k-1)的un

poj 3661 Running (区间dp)

poj 3661题目链接 题意:锻炼,一共n分钟,每分钟可以选择跑步或者休息,第i分钟跑步可以跑d[i]米,并增加一点疲劳度,如果选择休息,那么每分

poj 1651 Multiplication Puzzle (区间dp)

poj 1651题目链接 题意:n个数,删掉a[i]的得分是a[i]*a[i-1]*a[i+1],两个端点的不允许删。问删完n-2个数得到的最小分数

poj 3280 Cheapest Palindrome (区间dp)

poj 3280 题目链接 题意:一个字符串,给出添加一个字符或者删掉该字符的花费,问最小的话费使得字符串变成回文串。 思路:dp[i][j]表示区间[i,j

light oj 1422 - Halloween Costumes (区间dp)

light oj 1422 题目链接 题意: 按顺序去参加舞会。每个舞会对衣服都有要求。可以连续穿好多件衣服。需要时候就脱下来,但是一旦脱下来,这件衣服就报废了。问最

poj 2955 Brackets(区间dp....括号匹配。。。人生第一道区间dp)

poj2955题目链接 题意:给出若干括号,问最大匹配数是多少。 思路:没有思路。我知道这是dp。。。然后其他就什么都不知道了。。。转移方程? 完

BZOJ 1649: [Usaco2006 Dec]Cow Roller Coaster (dp,类似01背包)

Time Limit: 5 Sec Memory Limit: 64 MB Submit: 504 Solved: 265 [Submit][Status][Discuss] Description The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 <= L <= 1,000). The roller coaster comprises a collection of some of the

BZOJ 1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 (BFS,DP)

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 451 Solved: 226 [Submit][Status][Discuss] Description 考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的,它们

BZOJ 1632: [Usaco2007 Feb]Lilypad Pond (BFS,dp)

1632: [Usaco2007 Feb]Lilypad Pond Time Limit: 5 Sec Memory Limit: 64 MB Submit: 496 Solved: 153 [Submit][Status][Discuss] Description Farmer John 建造了一个美丽的池塘,用于让他的牛们审美和锻炼。这个长方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1

BZOJ 1618: [Usaco2008 Nov]Buying Hay 购买干草 (完全背包)

1618: [Usaco2008 Nov]Buying Hay 购买干草 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 906 Solved: 456 [Submit][Status][Discuss] Description 约翰的干草库存已经告罄,他打算为奶牛们采购日(1≤日≤50000)磅干草. 他知道N(1≤N≤10

BZOJ 1617: [Usaco2008 Mar]River Crossing渡河问题 (DP)

1617: [Usaco2008 Mar]River Crossing渡河问题 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 837 Solved: 606 [Submit][Status][Discuss] Description Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河,但他们所有的渡河工具

BZOJ 1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛(DP)

1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1012 Solved: 553 [Submit][Status][Discuss] Description 奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走,试图找到整

BZOJ 1613: [Usaco2007 Jan]Running贝茜的晨练计划 (dp)

1613: [Usaco2007 Jan]Running贝茜的晨练计划 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1468 Solved: 706 [Submit][Status][Discuss] Description 奶牛们打算通过锻炼来培养自己的运动细胞,作为其中的一员,贝茜选择的运动方

最长上升子序列nlogn解法

首先回顾一下n^2的做法。 状态转移方程为dp[i] =max(1,dp[j]) (1=<j<=i-1&&a[i]>a[j]) for ( int i = 1 ; i <= n ; i++) cin>>a[i]; for ( int i = 1 ; i <= n ; i++) { dp[i] = 1; for ( int j = 1 ; j < i ; j++) { if

codeforces #338 div2 B || 615B Longtail Hedgehog

题目链接 题意:给出n个点,m条边,定义一条路径的价值为【路径长度*(路径终点的度)】,求最大价值。 思路:一月份的时候写过一个回溯。。。TLE

ural 1057. Amount of Degrees (b进制数位dp)

题目链接 题意:设条件A为一个数恰好是k个互不相同的b的整数次幂的和,问某一个区间内满足条件A的数的个数是有多少个。 Example. Let _X_=15, _Y_=20, _K_=2, _B_=2. By this example 3 numbers are the

hdu 4734 F(x) (数位dp)

题目链接s 题意:将一个10进制数x按照2进制展开后得到的值设为f(x)…现在给出a,b(10^9)问【0,b】中满足f[x]&

bc #75 C || hdu 5642 King's Order (数位dp)

hdu5642题目链接 题意:问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上,则这个字符串为非法。否则