posts - 225, comments - 62, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

用C++实现滚动数组

Posted on 2007-08-01 00:45 魔のkyo 阅读(1089) 评论(1)  编辑 收藏 引用 所属分类: DataStucture
很多DP都可以节省内存，一般通过滚动数组的方法，下面是一个M行的滚动数组，可以看到实现得非常优雅
const int M=2;
double _dp[M][100000+1];

struct{
    double* operator [](int i){
        return _dp[i%M];
    }
}dp; 

Feedback

# re: 用C++实现滚动数组  回复  更多评论   

2007-09-20 11:24 by BNJ
在dp中有时需要对一个阶段的f[]整体赋初值，用普通数组的话可以一次性memset,但此方法滚动时必须在dp计算过程中，每计算一个阶段手工memset一次，否则前M个阶段的数据有可能会干扰计算。我吃过亏。。。

P.S.这种方法最美，只不过N多人不会用
只有注册用户登录后才能发表评论。