博客首页 → DP

最新文章列表

Poj 2250 Compromise

Compromise Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 4965   Accepted: 2266   Special Judge Description ...
DP 
zhuchuanshua 评论(0) 有6人浏览 2012-08-28 10:08

poj 1837 dp+01背包

题意，给出 n 个 挂钩的位置 ，- 表示在左边，+ 表示在右边，再给出m 个 砝码，现在要求 有多少种方法 能使 天平 平衡 思路，dp[i][j]表示挂 i 个砝码 力矩达到 j 的方法数，dp[i][j+hook[k]*val[i]]+=dp[i-1][j];也就是 dp[i][j]=sigma(dp[i-1][j-hook[k]*val[i]]); #include<std ...
DP 
chulongya 评论(0) 有3人浏览 2012-08-27 17:49

Poj 2250 Compromise

Compromise Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 4965   Accepted: 2266   Special Judge Description ...
DP 
douxiangc 评论(0) 有4人浏览 2012-08-27 17:19

poj1160(Post Office)

      题目链接：http://poj.org/problem?id=1160       题意：有N个村庄，要在这N个村庄中建K个邮局，求如何布置这些邮局能使得所有村庄到离它最近的那个邮局的距离总和最小。 代码： #include<stdio.h> #include<string.h> #include<stdlib.h> #include< ...
DP 
guaiwanlut 评论(0) 有4人浏览 2012-08-25 15:31

poj1157(花店问题+经典DP)

     题目链接：http://poj.org/problem?id=1157      题意：花店有F种花，V个花瓶。花和花瓶的编号均为1...N；当店主将每种花放在不同的花瓶里时所产生的美学值是不同，现告诉你每种花放在每个花瓶时的美学值，求如何放，这F种花能够获得最大的美学值，最大是多少。要求编号较大的花必须放在编号较大的瓶子中。 代码： #include<stdio.h&g ...
DP 
myriji_ss 评论(0) 有10人浏览 2012-08-24 12:21

hdu 4389

数位DP 状态记录非常麻烦 #include<cstdio> #include<cstring> #define N 91 using namespace std; int n; int dp[11][N][N][N];//位数，各位和，模，余数 int tmp[11],ten[11]; void init(){ int i,mod,res,sum,now ...
dp 
yujing_yu 评论(0) 有5人浏览 2012-08-23 11:10

hdu 4389

数位DP 状态记录非常麻烦 #include<cstdio> #include<cstring> #define N 91 using namespace std; int n; int dp[11][N][N][N];//位数，各位和，模，余数 int tmp[11],ten[11]; void init(){ int i,mod,res,sum,now ...
dp 
teseyinzhi 评论(0) 有13人浏览 2012-08-23 00:14

再谈升/降序子序列——POJ1631

上一篇文章介绍了如何求解最长升/降序子序列的长度，这篇文章讨论另一个与升/降序子序列有关的问题。 问题：将一个序列划分成单调的子序列最少可划分成多少个？ 例如。序列：1、4、2最少可划分成2个单调递增的子序列：{1，2}、{4}或{1,4}、{2}； 乍一看，觉得这需要动规，其实这可以贪心。 在用动规求序列{1、4、2}的时候，我们要考虑的一个重要问题是，1是与4连接还是与2连接， ...
DP 
chuilengqi 评论(0) 有12人浏览 2012-08-22 09:28

poj 1742 多重背包

虽然说这题多重背包很明显，但是没有花一点时间是过不了的，TLE 了n次啊，一开始直接用 多重背包 做法直接上，结果T了，后来也看了一些别人的做法，真的是需要思考啊。。 因为这题是判断最后 是否 符合条件，因此没必要 记录 最优结果，因此只要 利用 bool （int就 TLE，各种yy）记录是否 满足条件就可以了。 在 01 背包中，dp[i]=dp[i]|dp[i-cost]，表示i的状态 ...
DP 
leili 评论(0) 有1163人浏览 2012-08-19 20:48

poj 1160 Post Office

经典动态规划题目，俺真的是太菜 了，推了好久都没推出来，最后只好学习网上大神们的报告才过的。。 dp[i][j]表示前 j 个村庄 建了i 个 邮局的最优解，cost[i][j]表示在i 和 j 之间 建立一个邮局 的最小代价，很明显，肯定是建在最中间的 那个村庄的位置上。。 那么我们可以得到 dp[i+1][j+k]=min{dp[i][j]+cost[j+1][j+k]} k+j&l ...
DP 
sansuzi88 评论(0) 有6人浏览 2012-08-19 19:34

poj 1014 多重背包

很明显，这题是多重背包，参见背包九讲就可以做出来了，然后有个小问题就是 背包九讲上面的 伪代码 有点小问题，就是 进行二进制拆分的时候，while(k<num)应该是 while(k<amount),不知道是不是我看的版本太旧了，背包不怎么会，在那边RE了无数次。。 #include<stdio.h> #include<string.h> #inclu ...
DP 
guotou555 评论(0) 有10人浏览 2012-08-18 15:01

poj1463-1A

题目大意，有一些节点，节点间有路，节点上放哨兵可以监视和此节点直接连接的节点。求用最少的哨兵，监视所有的节点，没有盲区。。。。   其 ...
dp 
wsp_java 评论(0) 有9人浏览 2012-08-18 14:27

poj1463-1A

题目大意，有一些节点，节点间有路，节点上放哨兵可以监视和此节点直接连接的节点。求用最少的哨兵，监视所有的节点，没有盲区。。。。   其 ...
dp 
jiangu66 评论(0) 有10人浏览 2012-08-18 10:56

hdu 4328 Cut the cake

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4328 题目大意：求同色最大矩形，颜色相间的最大正方形。 题目思路：这种程度的dp都没做出来，我太弱了。。枚举下底，直接处理大左界和右界即可，对于相间的，将行列和为奇数的反转，就转化为同色。话说高度为0的时候要特别注意啊！我开始的处理的方法会让他们的左右界到-1和m,如果不去除这种情况，会得到m* ...
dp 
aiguoniis 评论(0) 有11人浏览 2012-08-14 18:00

POJ 2184 Cow Exhibition 背包问题

来源：http://poj.org/problem?id=2184 题意：有一些奶牛，他们有一定的s值和f值，这些值有正有负，最后让保证s的和为非负且f的和为非负的情况下，s+f的最大值。 思路：背包问题，我们可以设dp[i][s]为前i头牛的s值为s时f的最大值，这就转化成了背包问题，即把s当成是体积，f当成是价值，而且可以成功的把二维转化成一维。又因为有负数的情况，所以我们可以都加上一个 ...
DP 
wangwangzhi 评论(0) 有23人浏览 2012-08-14 17:47

hdu 4328 Cut the cake

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4328 题目大意：求同色最大矩形，颜色相间的最大正方形。 题目思路：这种程度的dp都没做出来，我太弱了。。枚举下底，直接处理大左界和右界即可，对于相间的，将行列和为奇数的反转，就转化为同色。话说高度为0的时候要特别注意啊！我开始的处理的方法会让他们的左右界到-1和m,如果不去除这种情况，会得到m* ...
dp 
jsp555 评论(0) 有6人浏览 2012-08-14 17:11

poj 2192 记忆化&dfs

给三个串，问 第三个串能否 由前两个串构成。。 dfs+剪枝。。 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxn=210; char sa[maxn],sb[max ...
DP 
yiheng 评论(0) 有840人浏览 2012-08-13 14:36

poj 2192 记忆化&dfs

给三个串，问 第三个串能否 由前两个串构成。。 dfs+剪枝。。 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxn=210; char sa[maxn],sb[max ...
DP 
tiebake 评论(0) 有12人浏览 2012-08-13 11:29

poj 2250 最长公共子序列

记录路径的最长公共子序列。。 简单dp，开一个pre数组记录路径，由于 dp[i][j]只能有三种状态推过来，即dp[i-1][j-1],dp[i][j-1],dp[i-1][j],那么我们可以将pre[i][j]分别设为 0  1   2 ，最后只要递归扫一遍就可以了。。 #include<iostream> #include<sstream> #include ...
DP 
yiheng 评论(0) 有1090人浏览 2012-08-12 14:12

HDU1114 完全背包

完全背包： 完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 完全背包按其思路仍然可以用一个二维数组来写出： f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v} 同样可 ...
java完全背包dp 
believexkx 评论(0) 有1014人浏览 2012-08-11 20:51

最近博客热门TAG

Java(141747) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54785) Web(54513) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics