AcWing 1214. 波动数列

2021-02-12 03:15

阅读：411

标签：include 注意 namespace names can 正数因此 ++ win

原题链接

考察:背包dp

错误思路:

f[i,j] j表示和

此思路必错,会MLE.

正确思路:

需要转换式子.已知 x + x+d₁ + x+d₁ +d₂+x+d₁+d₂+d₃...=s 等价于 nx+(n-1)d₁+(n-2)d₂+.. = s. s与n已知,d在a与b徘徊,而x的范围太广,因此可以考虑用其他变量表达x即

nx = s-(n-1)d₁-(n-2)d₂...d的取值是a与b.s与后面的式子同余.因此可以不知道x的值的问题下转化为背包问题.

注意只需要塞满n-1个物品即可.因为一共就n-1个d_i要取值

坑点:

s可以取负值,因此注意余数要是正数

 1 #include  2 #include  3 #include 
 4 using namespace std;
 5 typedef long long ll;
 6 const int N = 1010,Mod = 100000007;
 7 int f[N][N];
 8 int Get_Mod(int n,int mod)
 9 {
10     return (n%mod+mod)%mod;
11 }
12 int main()
13 {
14     int n,s,a,b,t;
15     scanf("%d%d%d%d",&n,&s,&a,&b);
16     t = Get_Mod(s,n);
17     f[0][0] = 1;
18     for(int i=1;i)
19         for(int j=0;j//不能只取到t,因为下面的等式余数范围不清楚
20             f[i][j] = (f[i-1][Get_Mod(j-(n-i)*a,n)]+f[i-1][Get_Mod(j+(n-i)*b,n)])%Mod;
21     printf("%d\n",f[n-1][t]);
22     return 0;
23 }

AcWing 1214. 波动数列

标签：include 注意 namespace names can 正数因此 ++ win

原文地址：https://www.cnblogs.com/newblg/p/14388544.html

上一篇：API-Security-Checklist

下一篇：搬家第11天-149.Wincc V7.3 OWC Chart控件初步使用11-差距大变量曲线处理

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 1214. 波动数列
文章链接：http://soscw.com/index.php/essay/54271.html

亲，登录后才可以留言！

AcWing 1214. 波动数列

评论

热门文章

推荐文章

最新文章

置顶文章