题目内容

P4933

大意:求等差子序列总个数(包括长度为 1 或 2 的)

解题思路

dp,先考虑状态的设计和转移。

不难发现,如果我们考虑第 i 个数,如果第 i 个数可以接上前面的某一个等差数列,那么答案就会增加前面等差数列的长度再加一,所以考虑将以 i 结尾的等差数列存进状态里面。

我们可以令 f_i 表示以 i 结尾的等差数列的长度,但是发现貌似不同的公差会造成不同的后效性,所以我们需要将公差也存储下来,即 f_{i,j} 表示以 i 结尾,公差为 j 的最长等差数列的长度,由于公差可能为负,故处理时要加上 20000 防止下标出锅

转移:

f_{i,k}\leftarrow f_{i,k}+f_{j,k}+1

同时 ans+=f[j][k]+1

注意取模就可以了

#include <cstdio>
#include <cctype>
using namespace std;

const int maxn=1005,mod=998244353;
int n,h[maxn];
int ans,f[maxn][20005<<1];

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        h[i]=read();
    for(int i=1;i<=n;i++)
    {
        ans++;
        for(int j=1;j<i;j++)
        {
            int cur=h[i]-h[j]+20000;
            f[i][cur]+=f[j][cur]+1;
            f[i][cur]%=mod;
            ans+=f[j][cur]+1;
            ans%=mod;
        }
    }
    printf("%d\n",ans%mod);
    return 0;
}
最后修改日期: 2020年3月28日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。