地精部落 – HYSBZ 1925(波动数列+DP)

来源: 地精部落 – HYSBZ 1925 – Virtual Judge

大视野的题都好难啊啊啊
参考了网上的题解,做这道题首先要知道几个性质
首先,题目要求的数列是一个波动数列,就是一个大一个小……波动嘛
然后就是波动数列的三个性质了:
性质一:波动数列中如果 i 与 i + 1 不相邻,那么交换这两个数依然是一个波动数列并且!方案数相同!!!不知道怎么证明。。。
例如
1 2 4 3 5 交换 1 3 后变成 3 2 4 1 5
性质二:将波动数列中的每一个数 i 都替换成 n + 1 – i 新数列依然是一个波动数列,且波峰波谷相反。
性质三:波动数列具有对称性,也就是说一个波动数列你把他反过来看还是一个波动数列

回到这道题上来,dp[i][j]的含义是长度为 i 的,以j为首且为山峰的数量
首先,当 j 与 j-1 不相邻的时候,由性质一可得,dp[i][j]=dp[i][j-1]
然后当 j 与 j-1 相邻的时候,数列一定是这样的 j j-1 ……………,也就是以j-1为首并且j-1为山谷的数量,所以,dp[i][j]=dp[i-1][i-(j-1)](用性质三将山谷变为山峰)。
综合两种情况就可以得出转移方程
dp[i][j]=dp[i][j-1]+dp[i-1][i-(j-1)]
最终的结果要*2因为我们算的是第一个数字是山峰的方案数,还有数量完全相同的,第一个数为山谷的方案呢。
因为当前状态i只会由i和i-1两个状态推出,所以代码中用到了滚动数组的优化。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int maxn=5005;

int n,mod;
int f[2][maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>mod;
    f[0][2]=1;//滚动数组优化,相当于f[2][2]=1
    for(int i=3;i<=n;i++)
    {
        for(int j=2;j<=i;j++)
        {
            f[i&1][j]=(f[i&1][j-1]+f[(i-1)&1][i-j+1])%mod;
        }
    }
    int ans=0;
    for(int j=2;j<=n;j++)
    {
        ans=(ans+f[n&1][j])%mod;
    }
    cout<<(ans<<1)%mod<<endl;
    return 0;
}

我感觉再做一次还是不会QAQ……

发表评论

电子邮件地址不会被公开。 必填项已用*标注