首页 > 其他 > 详细

[bzoj2287][poj Challenge]消失之物_背包dp_容斥原理

时间:2018-12-10 10:57:16      阅读:164      评论:0      收藏:0      [点我收藏+]

消失之物 bzoj-2287 Poj Challenge

题目大意:给定$n$个物品,第$i$个物品的权值为$W_i$。记$Count(x,i)$为第$i$个物品不允许使用的情况下拿到重量为$x$的方案数。

注释:$1\le n,val_i\le 2\cdot 10^3$。


想法:只需要用取模瞎**容斥一下就行了。

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2010 
using namespace std;
int a[N],f[N],g[N];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
int main()
{
	// freopen("thing.in","r",stdin);
	// freopen("thing.out","w",stdout);
	int n=rd(),m=rd(); for(int i=1;i<=n;i++) a[i]=rd();
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=a[i];j--) (f[j]+=f[j-a[i]])%=10;
	}
	for(int i=1;i<=n;i++)
	{
		memset(g,0,sizeof g);
		g[0]=1;
		for(int j=1;j<=m;j++)
		{
			printf("%d",((f[j]-g[j%a[i]])%10+10)%10);
			g[j%a[i]]=((f[j]-g[j%a[i]])%10+10)%10;
		}
		puts("");
	}
	// fclose(stdin); fclose(stdout);
	return 0;
}

小结:好题。

[bzoj2287][poj Challenge]消失之物_背包dp_容斥原理

原文:https://www.cnblogs.com/ShuraK/p/10094654.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!