2011计划
速度水一下刚才的srm492
今天比赛10：00开始，昨晚打了近三个小时实况，把cf翘掉了。
上午数据结构课，上了两节，翘了第三节屁颠屁颠地跑来做题。
div2就是好啊，题目都有思路。
第一题开始少看一个重要条件，浪费不少时间后过了，才200分
第二题想贪心，没思路，然后直接暴搞，查了好久都TLE，比赛后才发现我的goto直接跑到循环外，然后循环重新初始化了。。。
第三题貌似是MST，可惜我不会输入搞不定，遗憾啊！
cha人是我用白衣神的一一个思路变了一组简单的测试数据cha房间里两个1000pt,都失败了，损失惨重，后来有一个被系统干掉了，哎！
吃饭去了:(
windows下配置netbeans C++的几点细节
windows下配置netbeans C++的几点细节
最近在winXP和win7下配了几台机器，虽然按照网上的教程，但总是遇到各种问题，耽误了很多时间才解决，下面写下一点解决思路，供大家卡壳时参考。
（完整方法我就不转了，网上到处都是）
1. 一定要设置系统变量path，否则即使netbeans里正确指向了bin都不行，把mingw里bin的路径加进去，最好也把msys加进去，昨天帮人配机器，这是改正的最后一个bug
2.mingw和msys的安装路径不要用program files,因为这个路径里面有一个空格，有的时候会出问题
3.make一定要用msys的，但是netbeans里的总的路径设指向mingw就行了，make文件也不必移动到mingw的bin文件夹来，直接指向即可
4.注意编译器缺省值的修改，还有主工程的设置，别不小心在这个问题上究竟半天
大概就是这样，应该行了。
Self introduction and plan for winter holiday
滚动数组
昨晚做了一道题，开了一个int [5000][5000]的数组，OLE了，虽然可以用short [5000][5000]猥琐过,但毕竟只是特殊情况
正确的方法是滚动数组压缩存储，整理了一下网上的资料：
利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。不过经常还是用在DP题目中，因为DP题目是一个自下而上的扩展过程，我们常常用到是连续的解，前面的解往往舍弃！所以用滚动数组可以说是很有必要的。
滚动数组 举个简单的例子：
int i, d[100];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
d[i] = d[i - 1] + d[i - 2];
printf("%d", d[99]);
上面这个循环d[i]只依赖于前两个数据d[i - 1]和d[i - 2];
为了节约空间用滚动数组的做法
int d[3];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
d[i % 3] = d[(i - 1) % 3] + d[(i - 2) % 3];
printf("%d", d[99 % 3]);
注意上面的取余运算，我们成功地只保留了需要的最后3个解，数组好象在“
滚动”一样，所以叫滚动数组
//DP
对于二维也可以用（代码可能不太正确和完善，但是可以理解例子）:
int i,j,d[100][100];
for(i=1;i<100;i++)
for(j=0;j<100;j++)
d[i][j]=d[i-1][j]+d[i][j-1];
上面的d[i][j]只依赖于d[i-1][j],d[i][j-1];
运用滚动数组
int i,,j,d[2][100];
for(i=1;i<100;i++)
for(j=0;j<100;j++)
d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];
滚动数组实际是一种节省空间的办法，时间上没啥优势，多用于DP中，举个
例子吧：
一个DP，平常如果需要1000×1000的空间，其实根据DP的无后效性，可以开成2×1000，然后通过滚动，获得和1000×1000一样的效果。滚动数组常用于DP之中，在DP过程中，我们在由一个状态转向另一个状态时，很可能之前存储的某些状态信息就已经无用了，例如在01背包问题中，从理解角度讲我们应开DP[i][j]的二维数组，第一维我们存处理到第几个物品，也就是阶段了，第二维存储容量，但是我们获得DP[i],只需使用DP[i - 1]的信息，DP[i - k],k>1都成了无用空间，因此我们可以将数组开成一维就行，迭代更新数组中内容，滚动数组也是这个原理，目的也一样，不过这时候的问题常常是不可能缩成一维的了，比如一个DP[i][j]需要由DP[i - 1 ][k],DP[i - 2][k]决定，i<n，0<k<=10;n <= 100000000;显然缩不成一维,正常我们应该开一个DP[100000005][11]的数组，结果很明显，超内存，其实我们只要开DP[3][11]就够了DP[i%3][j]由DP[(i - 1)%3][k]和DP[(i - 2)%3][k]决定，空间复杂度差别巨大。
