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)$。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define LL long long

 #define N 2010

 #define P 1000000007LL

 using namespace std;

 int n;

 LL w[N],S[N],S2[N],f[N][][N];

 LL sum(LL S[],int l,int r)

 {

     if(l>r) return 0LL;

     LL ans = S[r]+P-S[l-];

     if(ans>=P) ans-=P;

     return ans;

 }

 int main()

 {

 //    freopen("test.txt","r",stdin);

     while(~scanf("%d",&n))

     {

         for(int i=;i<=n;i++) scanf("%lld",&w[i]);

         for(int i=;i<=n-;i++)

             for(int k=;k<=n;k++)

                 f[i][][k]=, f[i][][k]=, f[i][][k]=;

         for(int x1=;x1<=n;x1++)

             for(int x2=x1;x2<=n;x2++) f[][][x2]++;

         for(int x1=;x1<=n;x1++) f[][][x1]=;

         for(int i=;i<=n-;i++)

         {

             for(int k=;k<=n;k++)

             {

                 S[k]  = S[k-] +f[i-][][k];

                 S2[k] = S2[k-]+f[i-][][k]*(k-)*(k-);

                 S2[k] += f[i-][][k]*(k-);

                 S2[k] += f[i-][][k];

             }

             for(int k=;k<=n;k++)

             {

                 f[i][][k] += sum(S2,,k-);

                 f[i][][k] += f[i-][][k];

                 f[i][][k] += f[i-][][k];

                 f[i][][k] += f[i-][][k]*(k-)*(k-);

                 f[i][][k] += f[i-][][k]*(k-);

                 f[i][][k] += f[i-][][k];

                 f[i][][k] += sum(S,k+,n);

                 f[i][][k] += sum(S,k+,n)*k;

                 f[i][][k] += sum(S,k+,n)*k*k;

                 f[i][][k] = f[i][][k]%P * w[k]%P;

                 f[i][][k] = f[i][][k]%P * w[k]%P;

                 f[i][][k] = f[i][][k]%P * w[k]%P;

             }

         }

         LL ans=;

         for(int k=;k<=n;k++)

         {

             ans += f[n-][][k]*(k-)*(k-);

             ans += f[n-][][k]*(k-);

             ans += f[n-][][k];

             ans %= P;

         }

         cout << ans << endl;

     }

     return ;

 }

巴特西

Even Three is Odd

最新文章

热门文章