我是靠谱客的博主 娇气西装,最近开发中收集的这篇文章主要介绍Music Problem——01背包优化,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目链接:https://ac.nowcoder.com/acm/contest/5203/B

一道很不错的题目,综合了多个知识点。

题意:给你n个数,判断能否在这n个数中选一些数组成3600的倍数。

先给这个题的一般形式。

给你n个数,判断能否在这n个数中选一些数组成m的倍数。

(1 ≤ n ≤ 1e6, 2 ≤ m ≤ 1e3)

 然后我们可以发现一个01背包的解法(时间复杂度:O(n*m))

状态:dp[i][j]表示从1到i个数中能否选一些数组成m(0表示不可以,1表示可以)。

状态转移方程: dp[i + 1][(j + a[i]) % m] = 1 if dp[i][j] = 1

这里可以考虑用滚动数组优化一下。

但是这个时间复杂度肯定过不去,然后我们考虑优化。

有三种优化策略:二进制优化,bitset 或者 抽屉原理。

这里主要讲抽屉原理优化,其余的优化也会给出代码。

当n>=m的时候,肯定可以从这n个数中选择一些数组成m的倍数,直接输出YES即可。

为什么呢?利用一个取余的性质( (a + b) % mod = (a%mod +b%mod) % mod )以及抽屉原理.

下面给出证明(借鉴牛客上大佬的解释,链接:https://ac.nowcoder.com/acm/problem/blogs/13885):

定义sum数组为这n个数的前缀和数组,即sum[i]=a[1]+a[2]+.....a[i-1]+a[i]

分为两种情况考虑:

情况一:存在一个k(1 <= k <= n),使得sum[k] % m == 0,那么就得证;
情况二:对于任意的k(1 <= k <= n),都有sum[k] % m != 0,那么余数的种类只有 1 到 m-1 总共 m-1 种情况,但是有 m 个 sum,由抽屉原理可知必然有两个sum(假设为sum[i],sum[j],j > i)的余数相同。因此 (sum[j] - sum[i]) % m = (sum[j] % m - sum[i] % m) = 0;

代码实现:

#include<stdio.h>
#include<string.h>
using namespace std;
int a[150000];
int dp[3605],f[3605];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;scanf("%d",&n);
int m=3600;
memset(dp,0,sizeof(dp));
memset(f,0,sizeof f);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
if(n>3600) printf("YESn");
else{
for(int i=1;i<=n;i++){
for(int j=0;j<=m-1;j++) f[j]=dp[j];
for(int j=m-1;j>=1;j--)
if(dp[j])
f[(j+a[i]%m)%m]=1;
f[a[i]%m]=1;
for(int j=0;j<=m-1;j++) dp[j]=f[j];
}
if(dp[0]) printf("YESn");
else printf("NOn");
}
}
}

二进制优化的代码(来自已退役的cds学长):

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int V, s[3600], dp[18005];
void Alone(int use)
{
int v;
for(v=V;v>=use;v--)
{
if(dp[v-use]==1)
dp[v] = 1;
}
}
void Every(int use)
{
int v;
for(v=use;v<=V;v++)
{
if(dp[v-use]==1)
dp[v] = 1;
}
}
void Mulit(int n, int use)
{
int k;
k = 1;
while(k<n)
{
Alone(k*use%3600);
n -= k;
k *= 2;
}
Alone(n*use%3600);
}
int main(void)
{
int T, n, i, x;
V = 18000;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
memset(s, 0, sizeof(s));
for(i=1;i<=n;i++)
{
scanf("%d", &x);
x %= 3600;
s[x]++;
}
if(s[0])
{
printf("YESn");
continue;
}
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(i=1;i<=3599;i++)
{
if(s[i]!=0)
Mulit(s[i], i);
}
for(i=1;i<=5;i++)
{
if(dp[3600*i])
{
printf("YESn");
break;
}
}
if(i==6)
printf("NOn");
}
return 0;
}
/*
2
3
1800 3500 1900
6
3000 3000 3000 3000 3000 3000
*/

bitset优化:

#include <bits/stdc++.h>
using namespace std;
int T,n;
int a[100005];
int main(){
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (register int i=1; i<=n; ++i) scanf("%d",&a[i]),a[i]%=3600;
bitset<7201>dp;
for (register int i=1; i<=n; ++i)
{
dp|=(dp<<a[i])|(dp<<a[i]>>3600);
dp[a[i]]=1;
}
if (dp[0]) puts("YES");
else puts("NO");
}
return 0;
}

 

最后

以上就是娇气西装为你收集整理的Music Problem——01背包优化的全部内容,希望文章能够帮你解决Music Problem——01背包优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(59)

评论列表共有 0 条评论

立即
投稿
返回
顶部