dp – 第2页 – Tgotp-Blog

1019: [SHOI2008]汉诺塔

令f[i][j]表示第i个位置移动j个盘子到另外一个盘子上的步数。

令g[i][j]表示第i个位置移动j个盘子所到达的盘子。

 

c++代码如下:

 

P2258 子矩阵

暴力枚举选行的情况,然后dp求选列的最优情况。

f[i][j]表示选了i行,最后一次选的是j列的情况。。。

c++代码如下:

 

1592: [Usaco2008 Feb]Making the Grade 路面修整

按排序后的数组来搞一搞就好了。

枚举上一次选某种情况下的最小话费,同时可以加个优化,

即f[i][j]表示在第i个点,在b中选>=j 的编号的点的最小话费。

g[i][j]表示在第i个点,在b中选<=j 的编号的点的最小话费。

1:c++代码如下:
[crayo[......]

Read more

3039: 玉蟾宫

和以前做过的某道题有点像(好吧其实就是退化题)

令l[i][j]为能向左延伸的最大长度,r[i][j]同理up[i][j]代表向上最大延伸长度,

然后枚举每一个点就搞定了。

c++代码如下:

 

1270: [BeijingWc2008]雷涛的小猫

dp应该是一眼能看出来的。

然后就是方程,对于这道题来说方程应该很好列,主要是空间的处理,因为一个点可以由他上面一个点转移过来与上d层转移过来,

所以只用开z[2][N]代表z在上一层的最大值与f[N]代表在i层时最大数量。然后随便搞搞就好了。

c++代码如下:
[crayon-[......]

Read more

1042: [HAOI2008]硬币购物

dp + 容斥原理。

首先dp算出不计硬币的所有钱数的方案数,然后分别计算出每一种超的情况,利用容斥原理解决问题,容斥的一块可以dfs可以用状压。

c++代码如下:

 

1801: [Ahoi2009]chess 中国象棋

怎么说呢,还是比较有思维含量的。

对于状态我们令f[i][j][k]为第i行 有 j 列有 1 个棋子, k列有 2个棋子 那么不放棋子的个数就是m - j - k

那么 一行肯定最多放 2 个棋子,也就是三种状态,放,放一个,放两个。

然后分别讨论:

1.不放就是上一次该状[......]

Read more

1833: [ZJOI2010]count 数字计数

数位dp

令f[i][j][k][e]代表f为 i 位,是否受该位限制,已有 k个 z 是否有前导零的方案数。

c++代码如下:

 

1237: [SCOI2008]配对

沙茶了。没看到a中,b中元素互不相同,还想用费用流做。。。。

令f[i]表示在 i 位置时最小花费。

首先放结论:

对于一个位置,最优情况只会是a[i]对应b[i],b[i-1],b[i-2]组合的情况。

证明:

对于一个位置,若a[i]与b[i-3]组合 , 那么ab[......]

Read more

P2111 考场奇遇

概率dp

这一次对的某种情况为上一次少一的概率*成功的概率 + 一样*不成功的概率

c++代码如下: