分析
基本思路:
首先这是一道动态规划题目,但一开始就想到的是搜索,所以就各种搜索剪枝,实际上都是徒劳。
像这种简单的DP题目一般都有两个特点:
-
长得和搜索题很像,甚至就能用搜索做
-
有一个大的吓人的数据
看清这两点,明确了思路,下面开始进入分析阶段:
- 按照题目要求,最终得到的序列的长度为$n$,和为$s$,并且后一项是前一项加$a$或$-b$,我们不妨将这个操作封装在一起,记作$P$操作,即$P=(a,-b)$。
- 设首项为x,可以得到一个等式$x+(x+P)+(x+2P)+…+(x+(n-1)P)=s$,将这个式子整理一下,就是$nx+P+2P+…+(n-1)P=s$,即$(s-(P+2P+…+(n-1)P))/n=x$。
- 我们不妨将最后一次操作拿出来单独考虑,最后一次操作要么是+a,要么是-b。我们设$f[i][j]$表示只考虑前$i$ 项,且当前的总和除以$n$的余数是$j$的方案的集合, 那么状态转移方程就可以是$f[i][j]=f[i - 1][j - a * i] + f[i - 1][j + b * i]$
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1005, MOD = 100000007;
int f[N][N];
int get_mod(int a, int b)
{
return (a % b + b) % b;
}
int main()
{
int n, s, a, b;
cin >> n >> s >> a >> b;
f[0][0] = 1;
for (int i = 1; i <= n - 1; i++)
{
for (int j = 0; j <= n - 1; j++)
{
f[i][j] = (f[i - 1][get_mod(j - a * i, n)] + f[i - 1][get_mod(j + b * i, n)]) % MOD;
}
}
cout << f[n - 1][s % n] << endl;
return 0;
}
我想问一下,等二层循环是在枚举余数吗?
代码有问题,最后输出应该是
acwing测试数据不全,不会WA,在蓝桥杯那里会WA掉一部分。
数据已加强,如果最后直接用
s % n
会被卡掉。