[NOIP2019模拟赛]序列（Sequence）

以你之姓@ 2023-06-01 06:09 1阅读 0赞

**题目大意**

有一个序列$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\]$$

然后记忆化搜索就好了

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 inline int read(){
     4     int ans=0,f=1;char chr=getchar();
     5     while(!isdigit(chr)){
        if(chr=='-')f=-1;chr=getchar();}
     6     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
     7     return ans*f;
     8 }const int M = 105,mod=1e9+7;
     9 int a[M],n,f[105][155][155];
    10 int DP(int x,int t1,int t2){
    11     if(x>=n&&t2<=0) return 1;
    12     if(f[x][t1][t2]!=-1) return f[x][t1][t2];
    13     int now=0;
    14     for(int i=0;i<=min(t1,t2);i++)
    15         now=(now+DP(x+1,t2-i,a[x+2]+i))%mod;
    16     return f[x][t1][t2]=now%mod;
    17 }
    18 int main(){
    19     freopen("sequence.in","r",stdin);
    20     freopen("sequence.out","w",stdout);
    21     int T=read();
    22     while(T--){
    23         n=read();
    24         for(int i=1;i<=n;i++)a[i]=read();
    25         memset(f,-1,sizeof(f));
    26         int Ans=DP(1,a[1],a[2]);
    27         printf("%d\n",Ans);
    28     }
    29     return 0;
    30 }
    31 /*
    32 3
    33 3
    34 2 3 1
    35 2
    36 2 2
    37 3
    38 1 2 3
    39 */

转载于:https://www.cnblogs.com/zhenglw/p/11337631.html