A - Many Formulae
题意： 给定一个长度为n的数组，在两个数之间加‘+’或‘-’，但是不能连续加两个‘-’号，在上述规则下，求出n个数在所有‘+’‘-’号组合的和，并取余109+7
思路： 建立两个二维数组
d
p
[
N
]
[
2
]
dp[N][2]
dp[N][2]，用
d
p
[
i
]
[
+
]
和
d
p
[
i
]
[
−
]
dp[i][+]和dp[i][-]
dp[i][+]和dp[i][−]分别表示当前这个数的符号为‘+’和‘-’的答案
w
a
y
[
i
]
[
+
]
和
w
a
y
[
i
]
[
−
]
way[i][+]和way[i][-]
way[i][+]和way[i][−]分别表示当前这个数的符号为
‘
+
’
和
‘
−
’
‘+’和‘-’
‘+’和‘−’的方案数。
当前符号为’+'时，上一个符号可为’+‘可为’-’，所以
w
a
y
[
i
]
[
+
]
=
w
a
y
[
i
−
1
]
[
−
]
+
w
a
y
[
i
−
1
]
[
+
]
way[i][+]=way[i-1][-]+way[i-1][+]
way[i][+]=way[i−1][−]+way[i−1][+]
d
p
[
i
]
[
+
]
=
d
p
[
i
−
1
]
[
+
]
+
w
a
y
[
i
−
1
]
[
1
]
∗
a
[
i
]
+
d
p
[
i
−
1
]
[
−
]
+
w
a
y
[
i
−
1
]
[
0
]
∗
a
[
i
]
dp[i][+]=dp[i-1][+]+way[i-1][1]*a[i]+dp[i-1][-]+way[i-1][0]*a[i]
dp[i][+]=dp[i−1][+]+way[i−1][1]∗a[i]+dp[i−1][−]+way[i−1][0]∗a[i]
因为当前第
i
i
i号数字位置符号为‘+’，那现在的得数，就是前面
i
−
1
i-1
i−1个数各种组合所得数，加上当前这个值，因为是在不同的合法组合中加上的
a
[
i
]
a[i]
a[i]，所以加上的是不同的方案数
∗
a
[
i
]
*a[i]
∗a[i]
当前符号位’-'时，上一个符号只能为’+’，所以
w
a
y
[
i
]
[
−
]
=
w
a
y
[
i
−
1
]
[
+
]
way[i][-]=way[i-1][+]
way[i][−]=way[i−1][+]
d
p
[
i
]
[
−
]
=
d
p
[
i
−
1
]
[
+
]
−
w
a
y
[
i
−
1
]
[
+
]
∗
a
[
i
]
dp[i][-]=dp[i-1][+]-way[i-1][+]*a[i]
dp[i][−]=dp[i−1][+]−way[i−1][+]∗a[i]
因为当前第
i
i
i号数字位置符号为‘-’，那现在的得数，就是前面
i
−
1
i-1
i−1个数各种组合所得数，减去当前这个值，因为是在不同的合法组合中减去的
a
[
i
]
a[i]
a[i]，所以减去的是不同的方案数
∗
a
[
i
]
*a[i]
∗a[i]
对于取模，为了防止出错，我基本在每一步运算中都取模了，并把数组考了long long
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int n;
ll dp[N][2], w[N][2];
ll a[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
dp[1][0] = a[0];
w[1][0] = 1;
for (int i = 1; i < n; i++) {
dp[i + 1][0] = (dp[i][0] + dp[i][1]) % mod + (a[i] * w[i][0]) % mod +(a[i] * w[i][1]) % mod;
dp[i + 1][1] = (dp[i][0] - a[i] * w[i][0] + mod) % mod;
w[i + 1][0] = (w[i][0] + w[i][1]) % mod;
w[i + 1][1] = w[i][0];
}
printf("%lld\n", (dp[n][0] + dp[n][1]) % mod);
return 0;
}
To be continued
如果你有任何建议或者批评和补充，请留言指出，不胜感激