NOIP模拟 2018.7.30 T2
hicc0305
2018-07-30 15:45:52
------------
非常妙的一个题目，你怎么也看不出来这是到背包问题。。
我们把问题转化一下：
设e[i]=a[i]+add[i],则0<=add[i]<=b[i]-a[i],则原来的两个式子可以转化成：
1.sigma(a[i]×c[i])+sigma(add[i]×c[i])=0 -> sigma(add[i]×c[i])=-sigma(a[i]×c[i])
2.sigma(a[i]×d[i])+sigma(add[i]×d[i])
而sigma(a[i]×c[i])和sigma(a[i]×d[i])是定值，我们这样就可以吧这个问题转化成背包问题了。你有n种物品，第i种有b[i]-a[i]个，价值为d[i]，体积为c[i]的东东，背包体积为sigma(a[i]×c[i])，要让总价值最大。多重背包啦
然后。。。说是要单调队列优化、二进制优化。。然而没优化也过了。。
```cpp
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,pls=0,val=0;
int a[2100],b[2100],c[2100],d[2100];
int add[2100],f[210000];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
val+=-a[i]*c[i];
add[i]=b[i]-a[i];
pls+=a[i]*d[i];
}
memset(f,-0x7f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
for(int k=1;k<=add[i];k++)
for(int j=val;j>=c[i];j--)
f[j]=max(f[j],f[j-c[i]]+d[i]);
printf("%d",f[val]+pls);
fclose(stdin);
fclose(stdout);
return 0;
}
```