[NOIP2019模拟赛]序列（Sequence）

题目大意

有一个序列$A_i$

　　• 对于 i ≥ 1，如果有$ A_i > 0、A_{i+1}> 0$ 且存在 $A_{i+2}$，那么法老可以令$ Ai$ 和 $A_{i+1}$ 减一，并令$ A_{i+2}$ 加一。

　　 • 如果 $A_{i+2}$ 不存在，但是其余两个条件满足，那么法老仍然可以令 $A_i$ 和 $A_{i+1}$ 减一。此时这两个元素位于序列尾端，法老需要在序列尾端加入一个新的元素，其值为 1。

问有多少可能存在的不同的序列

分析:

　　考场上状态设计错了...搞了一个4维的乱七八糟的东西然后放弃了...

　　打的爆搜还过不了最后打表才拿了20pts

　　记f[i][x][y]为当前是第i个位置，当前值为x，下一个值为y

　　转移方差：$$f[i+1][y+t][a[i+2]-t]+=f[i][x][y]$$

　　然后记忆化搜索就好了

 #include<bits/stdc++.h>

 using namespace std;

 inline int read(){

     int ans=,f=;char chr=getchar();

     while(!isdigit(chr)){if(chr=='-')f=-;chr=getchar();}

     while(isdigit(chr)) {ans=(ans<<)+(ans<<)+chr-;chr=getchar();}

     return ans*f;

 }const int M = ,mod=1e9+;

 int a[M],n,f[][][];

 int DP(int x,int t1,int t2){

     if(x>=n&&t2<=) return ;

     if(f[x][t1][t2]!=-) return f[x][t1][t2];

     int now=;

     for(int i=;i<=min(t1,t2);i++)

         now=(now+DP(x+,t2-i,a[x+]+i))%mod;

     return f[x][t1][t2]=now%mod;

 }

 int main(){

     freopen("sequence.in","r",stdin);

     freopen("sequence.out","w",stdout);

     int T=read();

     while(T--){

         n=read();

         for(int i=;i<=n;i++)a[i]=read();

         memset(f,-,sizeof(f));

         int Ans=DP(,a[],a[]);

         printf("%d\n",Ans);

     }

     return ;

 }

 /*

 3

 3

 2 3 1

 2

 2 2

 3

 1 2 3

 */

巴特西

[NOIP2019模拟赛]序列（Sequence）

最新文章

热门文章