jzoj4916. 【GDOI2017模拟12.9】完全背包问题（背包+最短路）

题面

题解

考场上蠢了……这么简单的东西都想不到……

首先排序加去重。

先来考虑一下，形如

\[a_1x_1+a_2x_2+...a_nx_n=w,a_1<a_2<...<a_n,x_i\geq 0
\]

的方程该怎么判断是否有解

首先，把两边都放到模\(a_1\)的意义下，就是

\[a_2x_2+...a_nx_n\equiv w\pmod{a_1}
\]

然后是一个神仙的转化，我们设有\(a_1\)个点，分别代表\(0,1,...,a_1-1\)，对于每一个点\(u\)，都连出去\(n-1\)条边，分别连向\((a+a_i)\%a_1\)，代价为\(a_i\)。那么我们对这个图跑一遍最短路，如果\(dis_{w\%a_1}\leq w\)，那么显然可以用这条最短路上的所有边加上若干个\(a_1\)构成\(w\)，否则的话肯定不行

那么对于大于等于\(L\)的部分我们可以暴力\(dp\)，设\(dp_{i,j}\)表示选了\(i\)个数，其中这\(i\)个数的和模\(a_1\)后为\(j\)（\(a_1\)就是最小的数），这\(i\)个数的和最小是多少，直接大力转移即可。

最后用\(dp_{i,j}\)更新\(dis_j\)，然后从每一个不为\(inf\)的\(dis_j\)出发，以所有\(a_i< L\)为边，跑多源最短路就行了

ps：其实严格来说如果\(a_1\geq L\)的话会发现上面的做法是错的，不过错的只有最短路那部分，暴力\(dp\)还是正确的，所以忽视这一点也没问题

//minamoto

#include<bits/stdc++.h>

#define R register

#define ll long long

#define inf 0x3f3f3f3f

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

ll read(){

    R ll res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=55,M=10005;

struct node{

	int u,d;

	node(){}

	node(R int U,R int D):u(U),d(D){}

	inline bool operator <(const node &b)const{return d>b.d;}

};priority_queue<node>q;

bitset<N*M>f[N];int a[N],vis[M];

int n,m,p,l,c,lim,u,v;ll w,dis[M],dp[N][M];

void mdzz(){

	memset(dis,0x3f,sizeof(dis));

	fp(i,0,a[1]-1){

		fp(j,0,c)cmin(dis[i],dp[j][i]);

		if(dis[i]!=inf)q.push(node(i,dis[i]));

	}

	while(!q.empty()){

		u=q.top().u,q.pop();

		if(vis[u])continue;vis[u]=1;

		fp(i,2,p)if(cmin(dis[v=(u+a[i])%a[1]],dis[u]+a[i]))q.push(node(v,dis[v]));

	}

}

int main(){

//	freopen("testdata.in","r",stdin);

	freopen("bag.in","r",stdin);

	freopen("bag.out","w",stdout);

	n=read(),m=read();

	fp(i,1,n)a[i]=read();

	sort(a+1,a+1+n),n=unique(a+1,a+1+n)-a-1;

	l=read(),c=read(),p=lower_bound(a+1,a+1+n,l)-a-1;

	memset(dp,0x3f,sizeof(dp));

	dp[0][0]=0;

	fp(i,p+1,n)fp(k,0,c-1)fp(j,0,a[1]-1){

		v=(j+a[i])%a[1];

		cmin(dp[k+1][v],dp[k][j]+a[i]);

	}

	mdzz();

	while(m--){

		w=read();

		puts(dis[w%a[1]]<=w?"Yes":"No");

	}

	return 0;

}

巴特西

jzoj4916. 【GDOI2017模拟12.9】完全背包问题（背包+最短路）

题面

题解

最新文章

热门文章

巴特西

jzoj4916. 【GDOI2017模拟12.9】完全背包问题 （背包+最短路）

题面

题解

最新文章

热门文章

jzoj4916. 【GDOI2017模拟12.9】完全背包问题（背包+最短路）