111qqz的小窝

老年咸鱼冲锋!

[dp专题000]uva 10328 Coin Toss (java 大数+dp)(Unsolved)

题目链接

题意:问长度为n,每个位置由且仅有‘H’和’T’组成的序列中,至少有连续k个‘H’出现的方案数。

思路:不会做,参考了题解 不过没有完全搞懂。

根据题解,正面考虑比较麻烦,所以反面考虑。[j]

dp[i][j]表示长度为i,前面最后连续的‘H’的个数不超过j个的方案数。

考虑转移方程为:

总的情况为:dp[i][j] = dp[i-1][j] * 2;

但是其中有多考虑的情况,就是第i位是’H’,且i位之前的最后j个位置都是’H’(即从i-j位到第i-1位都是‘H’,此时第i-j-1位必然是’T’)

有i个硬币时,如果i < j+1,那么它对于i-1的情况来说,最后一个硬币的位置就可以随便放了。

如果i > j + 1,dp[ i ] [ j ]  = dp [ i – 1 ] [ j ] * 2 – x(不满足条件的部分)

然后我们来考虑这个x怎么求,既然是不满足条件,那么肯定是第i的位置放了H,前面的都是H,从而这些连续的H大于j。那么就考虑dp[ i – 1 – j – 1 ](中间这 j – 1 个(kk:疑似作者笔误。应该位j个)全为H,加上第i个H,就不满足条件了),所以:

dp [ i ] [ j ] = dp [ i – 1 ] [ j ] * 2 – dp [ i – j – 2 ] [ j ](kk:仍然不是很懂这个式子…)

那么我们就差最后一个了:i == j + 1的情况了。(因为 i – j – 2 就等于 -1 了,用递推公式会RE的)

这种情况只有一种,即是全是H。

那么它就为:dp [ i ] [ j ] = dp [ i – 1 ] [ j ] * 2 – 1

 

 

 

最后,要用到高精度,干脆写了java

 

 

 

 

 

 

hdu 3507 Print Article (斜率优化dp)

题目链接

题意:n个数,分成若干段,每段的代价为,求最小代价。

思路:dp。

状态方程很显然个鬼。。。

dp[i] 表示处理完前面i个数的最小代价。

dp[0] = 0 ;

dp[i] = min(dp[j]+(sum[i]-sum[j])^2) ( 0<j <i),sum[i]为a[i]的前缀和。

这复杂度是n^2的。。。然而n最大5E5…..boom….

 

斜率优化登场!

这篇博客讲得非常好

我们假设k<j<i。如果在j的时候决策要比在k的时候决策好,那么也是就是dp[j]+M+(sum[i]-sum[j])^2<dp[k]+M+(sum[i]-sum[k])^2。(因为是最小花费嘛,所以优就是小于)

两边移项一下,得到:(dp[j]+num[j]^2-(dp[k]+num[k]^2))/(2*(num[j]-num[k]))<sum[i]。我们把dp[j]-num[j]^2看做是yj,把2*num[j]看成是xj。

那么不就是yj-yk/xj-xk<sum[i]么?   左边是不是斜率的表示?

那么yj-yk/xj-xk<sum[i]说明了什么呢?  我们前面是不是假设j的决策比k的决策要好才得到这个表示的? 如果是的话,那么就说明g[j,k]=yj-jk/xj-xk<sum[i]代表这j的决策比k的决策要更优。

 

关键的来了:现在从左到右,还是设k<j<i,如果g[i,j]<g[j,k],那么j点便永远不可能成为最优解,可以直接将它踢出我们的最优解集。为什么呢?

我们假设g[i,j]<sum[i],那么就是说i点要比j点优,排除j点。

如果g[i,j]>=sum[i],那么j点此时是比i点要更优,但是同时g[j,k]>g[i,j]>sum[i]。这说明还有k点会比j点更优,同样排除j点。

排除多余的点,这便是一种优化!

 

接下来看看如何找最优解。

设k<j<i。

由于我们排除了g[i,j]<g[j,k]的情况,所以整个有效点集呈现一种上凸性质,即k j的斜率要大于j i的斜率。

这样,从左到右,斜率之间就是单调递减的了。当我们的最优解取得在j点的时候,那么k点不可能再取得比j点更优的解了,于是k点也可以排除。换句话说,j点之前的点全部不可能再比j点更优了,可以全部从解集中排除。

 

于是对于这题我们对于斜率优化做法可以总结如下:

1,用一个单调队列来维护解集。

2,假设队列中从头到尾已经有元素a b c。那么当d要入队的时候,我们维护队列的上凸性质,即如果g[d,c]<g[c,b],那么就将c点删除。直到找到g[d,x]>=g[x,y]为止,并将d点加入在该位置中。

3,求解时候,从队头开始,如果已有元素a b c,当i点要求解时,如果g[b,a]<sum[i],那么说明b点比a点更优,a点可以排除,于是a出队。最后dp[i]=getDp(q[head])。

 

代码:

 

hdu 4283 You Are the One (区间dp)

hdu 4283题目链接

题意:有N个人按顺序排成一排上台表演,每个都有一个num[]值,若在他是第k个上场的人,则会有num[]*(k-1)的unhappiness。台下有一个黑屋(stack),对每一个人,可以选择让他先进屋子或者直接上台。现在让你找到一个最优方案使得所有人的unhappiness之和最小。

思路:

我想对了的:

无。状态设计就错了。。。转移方程也就不可能对。。。

错的一塌糊涂。。。嗯。。基础题。。完全不会2333

参考题解:参考博客1
参考博客2

poj 3661 Running (区间dp)

poj 3661题目链接

题意:锻炼,一共n分钟,每分钟可以选择跑步或者休息,第i分钟跑步可以跑d[i]米,并增加一点疲劳度,如果选择休息,那么每分钟减少1点疲劳值。一旦开始休息,必须休息到疲劳值为0才能再次开始跑步。疲劳值不能超过m.第n分钟的时候疲劳值必须为0,否则之后会感觉身体被掏空。问n分钟最远多多远。

思路:

我能想到的:

  • dp[i][j]表示第i分钟疲劳度为j的时候能跑的最远距离
  • 初始化dp为0.
  • 最后的答案为dp[n][0]
  • 如果第i分钟跑步,转移方程为dp[i][j] = max(dp[i][j],dp[i-1][j-1]+d[i]);

我想错了的:

  • 休息的时候的转移方程应该是第i天刚好休息好时:dp[i][0]=max(dp[i-j][j],dp[i][0]) 而不是开始休息
  • 由于是第i天休息好时的状态,那么开始休息的时间是固定的(第i-j天),只进行一个转移,而不会影响中间的那些天

我想的不够好的:

  • 考虑到了可能最后几天为了疲劳度为0干脆就不跑,我的做法是取了所有的dp[i][0]的最大值。但是更好的做法似乎是dp[i][0] = dp[i-1][0]转移一下。

参考博客:参考博客

 

参考题解:

分析:先设dp[i][j]表示小明在i分钟,疲劳值为j时所能走的最远距离。

a)、先看dp[i][0]的情况,表示第i分钟时,疲劳值为0,考虑这个值由哪些情况得到,1、dp[i][0] = dp[i-1][0],这个没有任何问题。2、dp[i][0] = dp[i-j][j]。表示i-j分钟时的疲劳值为j,然后一直休息j分钟把疲劳值降成0。

b)、现在考虑dp[i][j]的情况,它可以由dp[i-1][j-1] + Di得到,表示第i分钟选择走Di。因为要保证没有后效性,所以只有这一种情况可以转移。

 

poj 1651 Multiplication Puzzle (区间dp)

poj 1651题目链接

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

思路:能想到设计状态dp[i][j]表示区间[i,j]的最小分数。然后就没思路了。 T T

参考了几篇题解,思路大概是,枚举最后剩下的那个数。

对于一个区间(l, r),如果最后删除的是k位置的数的话,将得到a[l]*a[k]*a[r]分,而要得到这个情况的前提是吧区间(l, k) 和(k, r)的中间数字删掉所以的转移方程是

DP(l, r) = DP(l, k) + DP(k, r) + a[l]*a[k]*a[r];

以及。。。初始化又想错了。。。

要注意。。初始化可能没办法一次完成。。。这道题的初始化就是分情况的。。。

对于区间长度不够的。。初始化为0.。

区间长度为3的。。初始化为a[i]*a[i+1]*a[i+2]。。

其他的初始化为正无穷。。

 

 

poj 3280 Cheapest Palindrome (区间dp)

poj 3280 题目链接

题意:一个字符串,给出添加一个字符或者删掉该字符的花费,问最小的话费使得字符串变成回文串。

思路:dp[i][j]表示区间[i,j]的字符串变成回文的最小花费。。。

这个可以想到。。dp[i][j] = dp[i+1][j-1] (a[i]==a[j])这个也可以想到。。。

增加和删除是等价的,所以取小的那个代价就行。。这个我也想到了。。

然后转移的地方没有特别明白。。。

和之前的找到一个划分的点k不同的是。。。

如果不等于。。

那么

这个方程可以理解。。。但是感觉自己想不出来 QAQ

以及。。我初始化写错了。。。

以为是求 最小值就初始化成了0x3f…

但是这样是错的。。。

具体见代码注释。。。

 

light oj 1422 – Halloween Costumes (区间dp)

light oj 1422 题目链接

题意:

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

 

思路:没有思路。我连这题是dp都看不出来。。知道是dp也一点思路都没。。虽然这道题是道区间dp的入门题。。。但是不怕被鄙视。。我一点也没思路。。

参考了10多篇题解。。。终于懂了一点。。

参考博客1
参考博客2
参考博客3
参考博客4

 

当a[i]和a[j]相等的时候    dp[i][j]=dp[i][j-1] 嗯,就这一个转移。然后就是区间dp的固定写法了。

这句话让我恍然大悟。。。难道。。都是套路?

 

dp[i][j]表示的是[i,j]之间最少需要的衣服数量。

初始化dp[i][i] = 1,表示每天都换一件新衣服,显然不优。

a[i]==a[j]时,dp[i][j] = dp[i][j-1] ,表示第j天不用新换衣服,

然后枚举划分区间的点k,分成[i,k]和[k+1,j]两部分,取所有情况中最好的(这大概就是区间dp的套路?)

 

 

 

 

poj 1141 Brackets Sequence (区间dp,括号匹配,记录路径)

poj 1141题目链接

 

题意:给出一个括号序列,要求添加最少的括号,使得这个序列变成合法的括号匹配,输出最后的序列。

思路:区间dp。。。有了那么一点思路。。。我们可以用dp[i][j]表示区间[i,j]的序列最少需要添加几个符号使得匹配。。转移的话。。。和之前差不多。。dp[i][j] = dp[i+1][j-1] (s[i]与s[j])匹配。。。不匹配的话也是找中间某个点。。。初始化的话。。要变成最大值。。。比较没思路的是输出括号序列这部分。。。

参考了这篇题解:参考题解

记录路径的思路是。。。记录转移的点。。。

cut[i][j]表示的是区间[i,j]的最优值是由点cut[i][j]这里划分得到的。。。

cut[i][j]为-1表示区间[i,j]的最优值不是从中间分成两部分得到。。。

打印路径的时候。。。如果[i,j]的长度小于等于0.。直接return.

如果长度为1.。。直接输出。。。

如果长度大于1.。。。要分这段区间是否中间有划分两种情况。。具体见代码。。。

 

 

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

poj2955题目链接

 

题意:给出若干括号,问最大匹配数是多少。

思路:没有思路。我知道这是dp。。。然后其他就什么都不知道了。。。转移方程? 完全没思路。。知道了转移方程。。。。嗯,还是不会。。。边界怎么写?状态怎么推?循环顺序? 循环次序?我一点思路都没有。。。。。

人生中第一道区间dp(这话我都说了不知道多少次了。。。每次都学不会。。。。sad)

我的dp水平和其他部分的水平还真是不匹配。。。

看了题解。。。自己写(抄)了一遍。。还是觉得好玄学。。。

细节见代码。

 

 

BZOJ 1652: [Usaco2006 Feb]Treats for the Cows (区间dp)

1652: [Usaco2006 Feb]Treats for the Cows

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 290  Solved: 226
[Submit][Status][Discuss]

Description

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time. The treats are interesting for many reasons: * The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats. * Like fine wines and delicious cheeses, the treats improve with age and command greater prices. * The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000). * Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a. Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally? The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

约翰经常给产奶量高的奶牛发特殊津贴,于是很快奶牛们拥有了大笔不知该怎么花的钱.为此,约翰购置了N(1≤N≤2000)份美味的零食来卖给奶牛们.每天约翰售出一份零食.当然约翰希望这些零食全部售出后能得到最大的收益.这些零食有以下这些有趣的特性:

•零食按照1..N编号,它们被排成一列放在一个很长的盒子里.盒子的两端都有开口,约翰每
  天可以从盒子的任一端取出最外面的一个.
•与美酒与好吃的奶酪相似,这些零食储存得越久就越好吃.当然,这样约翰就可以把它们卖出更高的价钱.
  •每份零食的初始价值不一定相同.约翰进货时,第i份零食的初始价值为Vi(1≤Vi≤1000).
  •第i份零食如果在被买进后的第a天出售,则它的售价是vi×a.
  Vi的是从盒子顶端往下的第i份零食的初始价值.约翰告诉了你所有零食的初始价值,并希望你能帮他计算一下,在这些零食全被卖出后,他最多能得到多少钱.

Input

* Line 1: A single integer,

N * Lines 2..N+1: Line i+1 contains the value of treat v(i)

Output

* Line 1: The maximum revenue FJ can achieve by selling the treats

Sample Input

5
1
3
1
5
2

Five treats. On the first day FJ can sell either treat #1 (value 1) or
treat #5 (value 2).

Sample Output

43

OUTPUT DETAILS:

FJ sells the treats (values 1, 3, 1, 5, 2) in the following order
of indices: 1, 5, 2, 3, 4, making 1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43.

题意:一列数,可以从两段取,每天取一个数,第t天取到第i个数的价值是t*v[i],问能取到的最大价值是多少。
思路:能看出是dp.不过状态表示这一步就错了。。。我想的是dp[i]表示第i天取能得到的最大价值。。。然后转移方程就推不对了23333.
实际上这种从两段搞的问题的状态,还是要两个变量来表示状态比较好。
dp[i][j]表示最左端为i,最右端为j能得到的最大价值。
而且这道题的划分状态也很厉害。反正我是没想到。
定义了k表示为当前剩余区间的长度。
容易知道k=j-i+1;
那么t=n+i-j,j = n-k+1;
像很多dp一样,这道题也需要倒着推。。。
也就是从长度为1的区间推到长度为n的区间。
转移方程为dp[i][j] = max(dp[i+1][j]+t*v[i],dp[i][j-1]*v[j])
(注意观察,(i,j)的状态是由(i+1,j)或者(i,j-1)得到的,因为是从里向外推。)

hdu 1160 FatMouse’s Speed (最长上升子序列)

FatMouse’s Speed

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10172    Accepted Submission(s): 4521
Special Judge

Problem Description
FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.
 

 

Input
Input contains data for a bunch of mice, one mouse per line, terminated by end of file.

The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.

Two mice may have the same weight, the same speed, or even the same weight and speed. 

 

 

Output
Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m[1], m[2],…, m[n] then it must be the case that 

W[m[1]] < W[m[2]] < ... < W[m[n]] and  S[m[1]] > S[m[2]] > … > S[m[n]]

In order for the answer to be correct, n should be as large as possible.
All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one. 

 

 

Sample Input
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
 

 

Sample Output
4
4
5
9
7
 

 

Source
 

 

Recommend
Ignatius
 
先排序,然后求一个最长上升子序列。
第一次做记录路径的题,比较无力。
调了很久,后来调到样例都不对整个人都无奈了。
可能也是调了太久的缘故,整个人比较烦躁,也忘记了题目中的那句“如果有多组接那么任意输出一种”,结果白白浪费了好久。sad
还是不要浮躁。
 
AC代码:

hdu 1114 – Piggy-Bank (完全背包)

F – Piggy-Bank

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid. 

But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs! 

 

Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it's weight in grams. 
 

Output

Print exactly one line of output for each test case. The line must contain the sentence “The minimum amount of money in the piggy-bank is X.” where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line “This is impossible.”. 
 

Sample Input

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
 
 
 
 
完全背包。
注意是要放满,但是由于想要的是value的最小值,所以不合法的状态要赋值成inf而不是-1

hdu 1087 – Super Jumping! Jumping! Jumping! (最长上升子序列)

E – Super Jumping! Jumping! Jumping!

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now. 

The game can be played by two or more than two players. It consists of a chessboard(棋盘)and some chessmen(棋子), and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path. 
Your task is to output the maximum value according to the given chessmen list. 

 

Input

Input contains multiple test cases. Each test case is described in a line as follow: 
N value_1 value_2 …value_N 
It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int. 
A test case starting with 0 terminates the input and this test case is not to be processed. 
 

Output

For each case, print the maximum according to rules, and one line one case. 
 

Sample Input

3
1 3 2
4
1 2 3 4
4
3 3 2 1
0
 

Sample Output

4
10
3
 
 
最长上升子序列。