题解 CF1000D 【Yet Another Problem On a Subsequence】

墨染琉璃殇 · 2020-10-08 00:09:04 · 题解

本蒟蒻又来发题解了......

因为是一道绿题，所以不是特别难，通过读题，我们可以发现，这是一道 DP 题，但是，这种颜色的题也肯定不会是裸的 DP ，所以我们需要做一点小小的调整。

思路如下：

我们可以定义一个 dp[i] ，考虑令 dp[i] 表示前 i 个数，第 i 个数为重要的数的方案数。如果没有答案，则 dp[i]=0 。

转移即为： dp[i]*C(j-i-1,a[i])->dp[j] ，其中 C(n,k) 为组合数。组合数可以通过 C(n,k)=C(n-1,k-1)+C(n-1,k) 预处理。

时间复杂度为 O(n^2) ，可以过。

然后，我们就可以得出答案了。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,c[2005][2005],a[1005],dp[1005];
int main()
{
    cin>>n;
    for (long long i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    c[0][0]=1;
    for (long long i=1;i<=n;i++)
    {
        c[i][0]=1;
        for (long long j=1;j<=i;j++)
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;//边处理边取模，不然要炸。
    }
    dp[0]=1;
    for (long long i=1;i<=n;i++)
    {
        dp[i]=1;
        for (long long j=i-1;j>=1;j--)
        {
            if (a[j]>0 && i-j+1>=a[j]+1)dp[i]=(dp[i]+dp[j-1]*c[i-j][a[j]])%mod;//状态转移方程。
        }
    }
    dp[n]--;
    if(dp[n]<0) dp[n]+=mod;
    cout<<dp[n];
    return 0;
}

思路借鉴老师