Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

dp方程是不是：f[i][j] = min{f[i-1][k]+(j+sta[i]-station[i-1]-k)*price[i-1])},对k枚举？另外，这题是单case么？

Posted by sunmoonstar_love at 2005-07-10 19:47:39 on Problem 2465

Followed by:

hawk大大,请帮我看一下吧，submit到吐血了，改到几乎和AC的一模一样了，谢谢！ (1395) sunmoonstar_love 2005-07-10 23:31:29
- 感觉方程好像不是这样的呢 (1511) frkstyc 2005-07-10 23:33:18
  - 方程是对的,我用下面的代码AC了 (1511) xfxyjwf 2005-07-11 00:16:02
    - 立方也能过啊，我还想了平方的 (1633) frkstyc 2005-07-11 00:18:14
      - 大概数据不很强吧 (0) xfxyjwf 2005-07-11 00:20:13
      - 能教教我，平方的么，现在写DP都只会立方的 (0) sunmoonstar_love 2005-07-11 00:41:04
        就是p[n][i]=min(p[n-1][i+d],p[n][i-1])+f啊，d是前后两站的距离，f是钱，然后滚动数组就行了 (0) frkstyc 2005-07-11 00:43:54
        原来高手都用滚动数组卡内存，一直没想到，只会傻呵呵地m*n的矩阵数表，又学到了 (0) sunmoonstar_love 2005-07-11 00:50:11
        之前好几次用滚动数组都砍掉2/3的时间，递推式简单的时候就这么写了，复杂的还是先大数组过了再说 (0) c0500448264 2005-07-11 00:52:45
        P[n][i]是到第n站，油为i时的最少费用，对f不是很明白，f = pri[n]？那方程是不是p[n][i]=min(p[n-1][i+d],p[n][i-1]+pri[i]) (0) sunmoonstar_love 2005-07-11 01:06:25
        f是一litre油要被油站抢劫多少，p是跑到第n个站之后剩i那么多油要多少钱 (0) frkstyc 2005-07-11 01:08:09
        前面抄错了 (0) frkstyc 2005-07-11 01:08:55
        谢谢你 (0) sunmoonstar_love 2005-07-11 01:10:29
        p[n][i]=min(p[n-1][i+d],p[n][i-1]+pri[i]) (19) luoyudong 2010-03-23 21:08:29
    - 谢谢你，能讲讲我错在哪了么，始终想不通为什么WA,WA了20+次 (1633) sunmoonstar_love 2005-07-11 00:33:11
      - 明白了，我对Impossible的判断不够强，郁闷了一晚上，谢谢各位指点~~~~~~~~ (0) sunmoonstar_love 2005-07-11 00:37:35
这题是单case，会出现Impossible么？ (0) sunmoonstar_love 2005-07-10 23:32:59
- 会的 (0) frkstyc 2005-07-10 23:33:28
- 才想到，POJ支持多文件的，一开始我还想偷懒不写判Impossible呢，真是自作自受。。。。。 (0) sunmoonstar_love 2005-07-11 00:39:54
  - 你把终点再加100mile就好了嘛 (0) frkstyc 2005-07-11 00:41:08

Post your reply here:

Home Page Go Back To top