百度网页版下载安装,优化整站,oa办公软件怎么使用,阿克苏建设网站题意#xff1a; 问题是对于所有的长度为n#xff0c;且$1ain$的整数序列求 $\prod_{i1}^{n-2}{max \{w_i,w_{i1},w_{i2}}\}$ 之和。 解法#xff1a; 首先设dp状态为 $f(i,j,k)$ #xff0c;长度为$i3$的#xff0c;最大值为k#xff0c;且最大值出现的位置集合…题意 问题是对于所有的长度为n且$1ain$的整数序列求 $\prod_{i1}^{n-2}{max \{w_i,w_{i1},w_{i2}}\}$ 之和。 解法 首先设dp状态为 $f(i,j,k)$ 长度为$i3$的最大值为k且最大值出现的位置集合为j的序列的乘积和。 显然可以由 $f(i-1,j2,k2)$ 转移到 $f(i,j,k)$做前缀和优化总效率$O(n^2 * 2^6)$ 重新设计dp状态改变j的定义j表示最大值最后出现的位置。 这样对于状态 $f(i,j,k)$我们确定了长度为$ij$的序列的值并且确定了$a(ij1)...a(i2)k$ 。 假设之前的三个数字最大值为$k2$之后的最大值为k这样的的话只要分为 $kk2, kk2, kk2$ 讨论即可得出答案。 再加以前缀和优化总效率$O(n^2)$。 1 #include iostream2 #include cstdio3 #include cstring4 5 #define LL long long6 #define N 20107 #define P 1000000007LL8 9 using namespace std;
10
11 int n;
12 LL w[N],S[N],S2[N],f[N][3][N];
13
14 LL sum(LL S[],int l,int r)
15 {
16 if(lr) return 0LL;
17 LL ans S[r]P-S[l-1];
18 if(ansP) ans-P;
19 return ans;
20 }
21
22 int main()
23 {
24 // freopen(test.txt,r,stdin);
25 while(~scanf(%d,n))
26 {
27 for(int i1;in;i) scanf(%lld,w[i]);
28 for(int i0;in-2;i)
29 for(int k1;kn;k)
30 f[i][0][k]0, f[i][1][k]0, f[i][2][k]0;
31 for(int x11;x1n;x1)
32 for(int x2x1;x2n;x2) f[0][2][x2];
33 for(int x11;x1n;x1) f[0][1][x1]1;
34 for(int i1;in-2;i)
35 {
36 for(int k1;kn;k)
37 {
38 S[k] S[k-1] f[i-1][0][k];
39 S2[k] S2[k-1]f[i-1][0][k]*(k-1)*(k-1);
40 S2[k] f[i-1][1][k]*(k-1);
41 S2[k] f[i-1][2][k];
42 }
43 for(int k1;kn;k)
44 {
45 f[i][2][k] sum(S2,1,k-1);
46 f[i][1][k] f[i-1][2][k];
47 f[i][0][k] f[i-1][1][k];
48 f[i][2][k] f[i-1][0][k]*(k-1)*(k-1);
49 f[i][2][k] f[i-1][1][k]*(k-1);
50 f[i][2][k] f[i-1][2][k];
51 f[i][0][k] sum(S,k1,n);
52 f[i][1][k] sum(S,k1,n)*k;
53 f[i][2][k] sum(S,k1,n)*k*k;
54 f[i][0][k] f[i][0][k]%P * w[k]%P;
55 f[i][1][k] f[i][1][k]%P * w[k]%P;
56 f[i][2][k] f[i][2][k]%P * w[k]%P;
57 }
58 }
59 LL ans0;
60 for(int k1;kn;k)
61 {
62 ans f[n-2][0][k]*(k-1)*(k-1);
63 ans f[n-2][1][k]*(k-1);
64 ans f[n-2][2][k];
65 ans % P;
66 }
67 cout ans endl;
68 }
69 return 0;
70 } View Code 转载于:https://www.cnblogs.com/lawyer/p/6444890.html
