[Luogu]P4933 大师
本文最后更新于 292 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp4933/

题意

题目传送门

简单地说,题意就是:求选出的数列是等差数列的方案数。
特别地,单个数和两个数也算作等差数列。

解法

求方案数常用方法,动态规划
设计状态,很容易想到公差肯定是状态中的一值,而结尾节点也是状态中一值,于是设计出状态:

$$ dp_{i,k}代表\texttt{以位置} i \texttt{结尾的等差数列,公差为} k \texttt{的方案数。} $$

那么转移方程:

$$ dp_{i,k} = \sum_{j < i} dp_{j,k} $$

即枚举前一个数 $j$,在该数后接上当前数。

然而如果这样转移,枚举 $i$ $j$ $k$,时间复杂度为 $O(n^2v)$,显然是不可接受的。
但事实上,并不需要枚举 $k$,因为一旦确定了 $i$ $j$,那么确定数列结尾两数,公差也确定了。
因此改良转移方程为:

$$ dp_{i,h_i – h_j} = \sum_{j < i} dp_{j,h_i – h_j} $$

即可将复杂度降低到 $O(n^2)$,可以通过本题。
然而如何初始化又是一个难题,因为两个数一定可以构成一种方案,而单个数又可以构成一种方案,那么初始化相当麻烦、毫无头绪。
可能只有笔者这样吧
因此重新定义状态,定义为:

$$ dp_{i,k} 代表以位置 i 结尾的等差数列,公差为k且不包含当前单个数的方案的方案数。$$

也就是不计入单个数的方案数,放在最后计算。
那么在转移时,由于 $ dp_{j,h_i – h_j} $ 不包含单个 $j$ 的方案,但事实上可以从 $j$ 单个数转移到 $i,j$ 两个数的方案。
因此需要将这种方案计入,最后方程为:

$$ dp_{i,h_i – h_j} = \sum_{j < i} dp_{j,h_i – h_j} + 1 $$

代码

由于公差可能是负数,因此加上一个 maxv 来解决负数问题。
统计答案时由于直接遍历可能超时,因此在每次计算方案数时都计入 ans 中即可。

#include <cstdio>
using namespace std;
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
const int maxn = 1010;
const int maxv = 2e4 + 10;
const int mod = 998244353;
int n;
int h[maxn];
int f[maxn][maxv << 2];
long long ans = 0;
int main()
{
    read(n);
    for(int i = 1;i<=n;++i)
        read(h[i]);
    for(int i = 1;i<=n;++i)
    {
        for(int j = i-1;j;--j)
        {
            f[i][h[i] - h[j] + maxv] = (f[i][h[i] - h[j] + maxv] + f[j][h[i] - h[j] + maxv] + 1) % mod;
            ans = (ans + f[j][h[i] - h[j] + maxv] + 1) % mod;
        }
    }
    printf("%lld",(ans + n) % mod);
    return 0;
}
本文标题:[Luogu]P4933 大师
本文作者:Clouder
本文链接: https://www.codein.icu/lp4933/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇