随笔 - 87  文章 - 279  trackbacks - 0
<2006年10月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214290
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

pku 1014   已做
pku 1037   
pku 1050   已做
pku 1088   已做
pku 1141   已做
pku 1159   已做
pku 1163   已做
pku 1322   AC
                  看到题目就害怕,概率的-_-结果分析之下原来也不难
                  状态d[i][j]表示有j种颜色,拿了i个巧克力的最优值
                  方程: d[i+1][j+1] = d[i][j]*(c-j)/c;               (c为总颜色数)
                            d[i+1][j-1] = d[i][j]*j/c;
                  由于只是保留3位小数,所以加优化if (n>1000) n = 1000+n%2; //至于为什么要分奇偶性,这个还不太懂-_-这道算是ac一半而已
pku 2904   AC
                 
dp[k][i][j]表示k个邮筒时候放鞭炮数为i..j时候的最优值
                 
转移方程为:
                  dp[k][i][j] = min{t+max(d[k-1][i][t-1],d[k][t+1][j])};
                 
状态转移时候就是考虑选t个鞭炮放时候爆或不爆
pku 1458   已做
pku 1579   已做 
pku 1695   AC 
                 d[i][j][k]表示到达第i个点时候另外两辆车分别在点j和k时候的最优值
                  方程: d[i+1][j][k] = min(d[i+1][j][k], d[i][j][k]+g[i][i+1]);
                               d[i+1][i][k] = min(d[i+1][i][k], d[i][j][k]+g[j][i+1]);
                               d[i+1][i][j] = min(d[i+1][i][j], d[i][j][k]+g[k][i+1]);
                  //初始条件d[1][1][1] = 0;

pku 1732   AC
                  线型模型,本想用trie的,结果用map偷懒了。
                  d[i] = min{d[j]} + 1      0<=j<i && j+1..i字符合法
pku 1953   已做
pku 1976   AC
                  先对区间做预处理, 后面不足的coaches补0;
                  d[k][j] = max{d[k-1][p]}+b[j];          0<=p<=j-m (b为处理后的区间数组,m是一台locomotiv的容量)
                  由单调性可以在状态转移时候保存前一次转移时候的最大值再和b[j-m]做比较,把O(n^2)压缩到O(n)的时间复杂度
pku 2386   已做
pku 2479   已做
pku 2951   已做
   
   
pku 3036   已做
pku 3014   已做
pku 2229   已做
pku 1185   AC
                  最经典的状态DP,我用三进制表示每行状态,然后递推,结果tle,分析之后,枚举出有效状态,再推, 1000ms左右,
                  还是不够 快, 张伟达的论文上有更快的算法。

pku 1276   AC
                  01背包

有空把以前的也再做一次!~   

posted on 2007-02-28 15:00 阅读(1465) 评论(2)  编辑 收藏 引用 所属分类: 算法&ACM

FeedBack:
# re: ghost_wei给的任务,练好DP,练好基本功 2007-03-11 03:10 oyjpart
太猛了!  回复  更多评论
  
# re: ghost_wei给的任务,练好DP,练好基本功 2007-08-04 23:09 flycat
大牛 1276的代码能不能发到偶的邮箱 ?
dh19862004@163.com  谢谢了!
我想了很久   没出来,比较挫!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理