英雄哪里出来 » 日志 » DP 的崛起
DP 的崛起
英雄哪里出来 发表于 2008-11-10 19:29:15
pku 2626 Chess Accepted
三维DP，dp[i][j][k]表示前i个人中选了j个白人和k个黑人的最大值
思路简单明了，每次走到第i对人的时候，要么选白人，要么选黑人，要么都不选
状态转移方程：
dp[i][j][k] = Max{ dp[i-1][j][k], dp[i-1][j-1][k] + p[i].x, dp[i-1][j][k-1] + p[i].y }
pku 1141 Brackets Sequence Accepted
二维DP，dp[i][j]保存从第i个字符到第j个字符的最少添加括号数，分情况记忆化搜索
1.dp[i][j] = Min{ dp[i][j], dp[i+1][j-1] }
str[i] == '(' && str[j] == ')' || str[i] == '[' && str[j] == ']'
2.dp[i][j] = Min{ dp[i][j], dp[i+1][j] }
str[i] == '(' || str[i] == '['
3.dp[i][j] = Min{ dp[i][j], dp[i][j-1] }
str[j] == ')' || str[j] == ']'
4.dp[i][j] = Min{ dp[i][k] + dp[k+1][j] } (i <= k <= j)
构造序列的时候和求最小值的时候一样，寻找最优子路径即可
pku 1260 Pearls Accepted
二维DP，dp[i][j]表示第i个物品选择第j种价格时 从第i个物品到最后一个物品的价格总和最小值
其中p[i].num和p[i].price分别表示第i个物品的数量和价格
第i个物品作为第一个选第j种价格时候的情况
1.dp[i][j] = Min{ dp[i][j], (p[i].num + 10) * p[j].price + dp[i+1][k] } (j < k <= n)
第i个物品和前一个物品一样选择第j种价格
2.dp[i][j] = Min{ dp[i][j], p[i].num * p[j].price + dp[i+1][j] }
pku 1404 I-Keyboard Accepted
三维DP，dp[i][j][e]表示第i个字母放在第j行第e个位置的最优解，最后统计
dp[L][K][e] (1<=e<=L) 中的最小值即可；
fre[i] 表示该字母的频率
于是有状态转移方程：
第i个字母放在第j行第一个位置时
1.dp[i][j][1] = Min{ dp[i-1][j-1][e] + fre[i] } (1 <= e <= L)
第i个字母放在第j行其他位置时
2.dp[i][j][e] = dp[i-1][j][e-1] + fre[i] * e;
三维DP，dp[i][j][k]表示前i个人中选了j个白人和k个黑人的最大值
思路简单明了，每次走到第i对人的时候，要么选白人，要么选黑人，要么都不选
状态转移方程：
dp[i][j][k] = Max{ dp[i-1][j][k], dp[i-1][j-1][k] + p[i].x, dp[i-1][j][k-1] + p[i].y }
pku 1141 Brackets Sequence Accepted
二维DP，dp[i][j]保存从第i个字符到第j个字符的最少添加括号数，分情况记忆化搜索
1.dp[i][j] = Min{ dp[i][j], dp[i+1][j-1] }
str[i] == '(' && str[j] == ')' || str[i] == '[' && str[j] == ']'
2.dp[i][j] = Min{ dp[i][j], dp[i+1][j] }
str[i] == '(' || str[i] == '['
3.dp[i][j] = Min{ dp[i][j], dp[i][j-1] }
str[j] == ')' || str[j] == ']'
4.dp[i][j] = Min{ dp[i][k] + dp[k+1][j] } (i <= k <= j)
构造序列的时候和求最小值的时候一样，寻找最优子路径即可
pku 1260 Pearls Accepted
二维DP，dp[i][j]表示第i个物品选择第j种价格时 从第i个物品到最后一个物品的价格总和最小值
其中p[i].num和p[i].price分别表示第i个物品的数量和价格
第i个物品作为第一个选第j种价格时候的情况
1.dp[i][j] = Min{ dp[i][j], (p[i].num + 10) * p[j].price + dp[i+1][k] } (j < k <= n)
第i个物品和前一个物品一样选择第j种价格
2.dp[i][j] = Min{ dp[i][j], p[i].num * p[j].price + dp[i+1][j] }
pku 1404 I-Keyboard Accepted
三维DP，dp[i][j][e]表示第i个字母放在第j行第e个位置的最优解，最后统计
dp[L][K][e] (1<=e<=L) 中的最小值即可；
fre[i] 表示该字母的频率
于是有状态转移方程：
第i个字母放在第j行第一个位置时
1.dp[i][j][1] = Min{ dp[i-1][j-1][e] + fre[i] } (1 <= e <= L)
第i个字母放在第j行其他位置时
2.dp[i][j][e] = dp[i-1][j][e-1] + fre[i] * e;
收藏:
QQ书签
del.icio.us
最新评论
-
2009-04-30 15:03:05 匿名 59.38.*.*
pku 1404 怎么做的呢？？细节方面很难考虑哈 T . T
-
2009-04-30 16:24:18 匿名 59.38.*.*
能不能告诉我怎么做的呢？纠结好久了
-
2009-04-30 16:31:23 匿名 59.38.*.*
我的email是tomtomdream@gmail.com
已经不行啦。。。 -
2011-01-11 16:01:12 匿名 10.8.*.* http://www.jordansforsale.cc
Her beauty has been the eternal classic ~
