首页 > 代码库 > Even Three is Odd
Even Three is Odd
题意:
问题是对于所有的长度为n,且$1<=ai<=n$的整数序列求 $\prod_{i=1}^{n-2}{max \{w_i,w_{i+1},w_{i+2}}\}$ 之和。
解法:
首先设dp状态为 $f(i,j,k)$ ,长度为$i+3$的,最大值为k,且最大值出现的位置集合为j的序列的乘积和。
显然可以由 $f(i-1,j2,k2)$ 转移到 $f(i,j,k)$,做前缀和优化,总效率$O(n^2 * 2^6)$
重新设计dp状态,改变j的定义,j表示最大值最后出现的位置。
这样对于状态 $f(i,j,k)$,我们确定了长度为$i+j$的序列的值,并且确定了$a(i+j+1)...a(i+2)<k$ 。
假设之前的三个数字最大值为$k2$,之后的最大值为k,这样的的话只要分为 $k>k2, k<k2, k=k2$ 讨论即可得出答案。
再加以前缀和优化,总效率$O(n^2)$。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 #define LL long long 6 #define N 2010 7 #define P 1000000007LL 8 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(l>r) return 0LL; 17 LL ans = S[r]+P-S[l-1]; 18 if(ans>=P) 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 i=1;i<=n;i++) scanf("%lld",&w[i]); 28 for(int i=0;i<=n-2;i++) 29 for(int k=1;k<=n;k++) 30 f[i][0][k]=0, f[i][1][k]=0, f[i][2][k]=0; 31 for(int x1=1;x1<=n;x1++) 32 for(int x2=x1;x2<=n;x2++) f[0][2][x2]++; 33 for(int x1=1;x1<=n;x1++) f[0][1][x1]=1; 34 for(int i=1;i<=n-2;i++) 35 { 36 for(int k=1;k<=n;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 k=1;k<=n;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,k+1,n); 52 f[i][1][k] += sum(S,k+1,n)*k; 53 f[i][2][k] += sum(S,k+1,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 ans=0; 60 for(int k=1;k<=n;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 }
Even Three is Odd
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。