洛谷 P1356 数列的整除性（DP）
题目传送门
https://www.luogu.com.cn/problem/P1356又是一道简单的 DP 题……
解题思路
设 表示前
个数，通过一系列操作的结果对
取模后的值为
这种情况是否可行（0 不可行，1 可行）。
对于每一个数 ，都有两种选择，一个是 +，一个是 -。
那么，转移方程自然就出来了：
或者
特别地，题目说了只在 2 个数间加符号，所以第一个数的符号是不能改变的。
另外注意：负数取模，要加绝对值。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int q;
int n,mod;
int f[10001][101];
int a[10001];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>q;
while(q--)
{
memset(f,0,sizeof f);
cin>>n>>mod;
for(int i=1;i<=n;i++)
cin>>a[i];
f[1][abs((a[1]+mod)%mod)]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<mod;j++)
{
if(f[i-1][j])
{
f[i][abs((j+a[i]+mod)%mod)]=1;
f[i][abs((j-a[i]+mod)%mod)]=1;
}
}
}
if(f[n][0])
cout<<"Divisible\n";
else
cout<<"Not divisible\n";
}
return 0;
}原文地址：https://blog.csdn.net/2403_87021226/article/details/144141797
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！