英文网站 模板,十八把网站做扇子,深圳最大的手机市场在什么地方,广汉做网站正题 题目大意
给出长度为nnn的序列a,b,c,da,b,c,da,b,c,d 求一个序列eee满足 (∑i1nei∗ci)0(e∈[ai..bi])(\sum _{i1}^ne_i*c_i)0(e\in [a_i..b_i])(i1∑nei∗ci)0(e∈[ai..bi]) 求 max{∑i1nei∗di}max\{\sum_{i1}^ne_i*d_i\}max{i1∑nei∗di} 解题思路
我…正题 题目大意
给出长度为nnn的序列a,b,c,da,b,c,da,b,c,d 求一个序列eee满足 (∑i1nei∗ci)0(e∈[ai..bi])(\sum _{i1}^ne_i*c_i)0(e\in [a_i..b_i])(i1∑nei∗ci)0(e∈[ai..bi]) 求 max{∑i1nei∗di}max\{\sum_{i1}^ne_i*d_i\}max{i1∑nei∗di} 解题思路
我们把这个转换成一个多重背包问题拿ai∼bia_i\sim b_iai∼bi个物品要求价格之和为000且价值最大。 我们可以发现对于每个物品我们都至少aia_iai个所有我们可以直接把aia_iai个丢进背包里然后每个物品数量变为bi−aib_i-a_ibi−ai个做多重背包。 要二进制压缩不然会TTT codecodecode
#includecstdio
#includealgorithm
#includecstring
#define N 210
using namespace std;
int n,m,tmp,num;
int a[N],b[N],c[N],d[N];
int w[10050],v[10050],f[100050];
int main()
{memset(f,0xcf,sizeof(f));f[0]0;scanf(%d,n);for(int i1;in;i){scanf(%d%d%d%d,a[i],b[i],c[i],d[i]);b[i]-a[i];tmpa[i]*d[i];m-a[i]*c[i];}for(int k1;kn;k)//二进制压缩{for(int i1;ib[k];i*2){w[num]c[k]*i;v[num]d[k]*i;b[k]-i;}if(b[k]) w[num]b[k]*c[k],v[num]d[k]*b[k];}for(int i1;inum;i)//背包for(int jm;jw[i];j--)f[j]max(f[j],f[j-w[i]]v[i]);printf(%d,f[m]tmp);
}
