天天一道dp-系列博客
开篇语:感觉dp是一个很玄学的东西,实验能否通过天天一道dp来找到诀窍。
本系列开篇于2021/1/1
我只管对峙天天一道,如果考试日大概什么事情,会提前做掉大概当天找个简朴的做,但不会延后做,真的延后做了就会钉到 羞耻柱 (空缺日纪录)上。
文章目次
正文
牛牛想起飞(2021/1/1-Day1)
牛客链接
dp[j]表现前i个数和为j的情况存不存在。存在就是1,不存在就是0
[code]const int N = 1e5+5;bool dp[N][101];int a[N],b[N];int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); IOS; int n,y; cin >> n >> y; rep(i,1,n) cin >> a; rep(i,1,n) cin >> b; dp[1][a[1]] = 1; dp[1][(a[1] + b[1])%y] = 1; dp[1][(a[1] - b[1] + y) % y] = 1; rep(i,2,n) { rep(j,0,100) { if(dp[i-1][j]) { dp[(j + a-b+y)%y] = 1; dp[(j + a+b)%y] = 1; dp[(j + a) % y] = 1; } } } // int ans = -1; per(j,100,0) { if(dp[n][j]) { cout |