保洁公司网站怎么做,科技设计网站有哪些内容,学科专业建设规划,vps 建网站 代理滚动数组详解 何为滚动数组#xff1f;滚动数组是如何优化空间的#xff1f;交替滚动例题#xff1a;来自某某轮廓线DP的题目 自我滚动(~~不如交替~~ 完结#xff01;#xff01;#xff01; (
宇宙免责任书#xff1a;我用的是C) 何为滚动数组#xff1f; 什么是滚动… 滚动数组详解 何为滚动数组滚动数组是如何优化空间的交替滚动例题来自某某轮廓线DP的题目 自我滚动(~~不如交替~~ 完结 (
宇宙免责任书我用的是C) 何为滚动数组 什么是滚动数组是会唱跳rap的数组吗其实滚动数组就是它名字的意思一直在滚动的数组。更形容的说就像一个滚轮在一个状态轴向前后滚动。那么滚轮大家都知道它是一个动态的东西那么放到代码中那其实就是一个数组像一个滚轮一样不断的向前递进但是递进的过程中并不关心我们的状态只注重结果换句话说这个数组只保存结果。 当然滚动数组只是一种优化手段通常用来优化我们的DP的空间偶尔下降点时间复杂度。 滚动数组是如何优化空间的
上文中提到滚动数组其实就是一个在动态滚动的数组它会在滚动的时候将浪费也就是可以省的空间给省下来。举个例子 d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] ] a [ i ] dp[i][j] max(dp[i-1][j], dp[i-1][j-1]]a[i] dp[i][j]max(dp[i−1][j],dp[i−1][j−1]]a[i]我们发现 d p [ i ] [ ] dp[i][ ] dp[i][]只与 d p [ i − 1 ] [ ] dp[i-1][] dp[i−1][]有关与前面 d p [ i − 2 ] [ ] , d p [ i − 3 ] [ ] . . . dp[i-2][],dp[i-3][]... dp[i−2][],dp[i−3][]...无关所以滚动数组就可以将它们这些空间省下来。 那么滚动数组该如何操作呢 可以分为两种交替滚动和自我滚动。
交替滚动 顾名思义就是两行数组交替的进行滚动: d p [ 2 ] [ i ] d p [ 0 ] [ i ] 和 d p [ 1 ] [ i ] 互相转移 dp[2][i]dp[0][i]和dp[1][i]互相转移 dp[2][i]dp[0][i]和dp[1][i]互相转移。这种方法的有点是简单特别简单只要你学过数组你就会而且代码十分明了不容易出错。 那么操作代码该如何写呢给出一个伪代码 for (日常枚举)
{交换数组 开始转移
}如上代码是不是看起来十分简单那么对于交换数组有两种方法第一异或第二直接swap。 好现在你已经会交替滚动了。 来个例题
例题来自某某轮廓线DP的题目
题目:HDU-4064 题解 那么好的这是一道轮廓线DP的题目但是我们今天的主题不是轮廓线而是滚动数组所以等到下次轮廓线DP的时候再重点说说吧。 先说本题主要做法吧当然是我们的轮廓线DP,但是在做的时候如果普通的做空间直飙1e8真的是太难受了。于是我们就要开始优化了。首先用上交 ~ 替 ~ 滚 ~ 动 ~的优化。
那么我们可以这么优化用异或高级点叫奇偶转变swap的一边去 异或就是我们的异或符号 ^ 那么我们知道异或是不同为1相同为0所以拿一个数去异或1如果是偶数秒变奇数如果是奇数秒变偶数。这是因为奇数末尾肯定为1偶数末尾肯定为0那么再异或1就改变奇偶性了。 操作就是如下
int cur 0;
cur ^ 1 //变 1就是变奇数了
cur ^ 1 //变 0就是变偶数了那么总代码就是可以写成如下样子热心肠的我把轮廓线的部分也给加上去了
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define m_p(i,j) make_pair(i,j)
#define pb push_back
#define pii pairint,int
#define mem(a,b) memset(a,b,sizeof(a))
#define fir first
#define sec second
const int eps 1e-8;
ll POW(int a, int b)
{ll sum 1;for (int i 1; i b; i) sum * a;return sum;
}
inline int read()
{int X0; bool flag1; char chgetchar();while(ch0||ch9) {if(ch-) flag0; chgetchar();}while(ch0ch9) {X(X1)(X3)ch-0; chgetchar();}if(flag) return X;return ~(X-1);
}
inline void write(ll X)
{if(X0) {X~(X-1); putchar(-);}if(X9) write(X/10);putchar(X%100);
}
const int mod 1e9 7;
int n, m;
string MP[15][15];
ll dp[2][(1 20)], P;
int cur;
int check(char a)
{if (a C) return 0;if (a R) return 1;return 2;
}
void dfs(int pos, int now_mask, int last_mask, ll sum, char left, int hang)
{if (pos m 1){sum (sum * dp[cur ^ 1][last_mask]) % mod;dp[cur][now_mask] (dp[cur][now_mask] sum) % mod;return ; }int tot 0;int num[10];char one[10], two[10], three[10];for (int i 0; i 4; i){if (pos ! 1 MP[hang][pos][i] ! left) continue;char right MP[hang][pos][(i 2) % 4];char up MP[hang][pos][(i 1) % 4];char down MP[hang][pos][(i 3) % 4];int flag 1;for (int j 1; j tot; j){if(right one[j] up two[j] down three[j]){flag 0;num[j];break;}}if (flag){one[tot] right;two[tot] up;three[tot] down;num[tot] 1;}}for (int i 1; i tot; i){int jlast_mask (last_mask * 3 check(two[i]));int jnow_mask (now_mask * 3 check(three[i]));dfs(pos 1, jnow_mask, jlast_mask, (sum * num[i]) % mod, one[i], hang);}
}
int main(){n read(), m read();for (int i 1; i n; i) for (int j 1; j m; j) cin MP[i][j];P POW(3, m);for (int i 0; i P; i) dp[0][i] 1;cur 0;for (int i 1; i n; i){cur ^ 1; //开始交替mem(dp[cur], 0);dfs(1, 0, 0, 1LL, z, i);}ll ans 0;for (int mask 0; mask P; mask) ans (ans dp[cur][mask]) % mod;write(ans); return 0;
}自我滚动(不如交替 你已经会交替滚动了开始上难度了----自我滚动 我们发现其实我们把二维转换为两个一维反正就0/1算成俩一维吧。 但是实际上海能进行优化。 就继续拿上面的 d p [ i ] [ j ] m a x ( . . . ) dp[i][j] max(...) dp[i][j]max(...)接着举例吧。 我们是可以接着优化。 我们发现它可以优化成一维只需要自己跟以前的自己转移就行了。 但是注 ~ 意 ~ ,若上述的转移在枚举j时一定要反过来枚举不然可能错因为它的结果是由同一个空间得到的可能会影响答案正确性。 那么给出上述那个转移的代码吧指dp[i][j] max…那个
for (int i 1; i n; i)
{for (int j m; j 1; --j){dp[j] max(dp[j], dp[j - 1] a[i]);}
}完结
恭喜你已经学会滚动数组了 [撒花✿✿ヽ(°▽°)ノ✿]
