abcd

【问题描述】
有4个长度为N的数组a,b,c,d。现在需要你选择N个数构成数组e，数组e满足
a[i]≤e[i]≤b[i]以及 Σe[i]*c[i]=0,并且使得Σe[i]*d[i]最大。
【输入格式】
输入文件名为abcd.in。
输入文件共 N+1 行。
第 1 行包含1个正整数N。
第 i+1 行包含4个整数a[i],b[i],c[i],d[i]。
【输出格式】
输出文件名为abcd.out。
输出共1行，包含1个整数，表示所给出公式的最大值。输入数据保证一定有解。
【输入输出样例1 1 】
abcd.in 
5
-1 1 2 5
-2 2 1 2
0 1 1 3
-2 -1 3 10
-2 2 3 9

abcd.out
2
【输入输出样例2 2 】
abcd.in 
10
1 10 1 7
-10 10 2 0
-10 10 2 2
-10 10 2 0
1 10 1 0
-10 10 2 0

10 10 2 0

1 10 1 0
-10 10 2 0
1 10 1 0

abcd.out
90
【输入输出样例3 3 】
abcd.in 
10
1 10 1 0
-10 10 2 2
-10 10 2 2
-10 10 2 2
1 10 1 0
-10 10 2 2
-10 10 2 2
1 10 1 0
-10 10 2 2
1 10 1 0

abcd.out
-4
【数据规模与约定】
对于 20%的数据，N≤10，-2≤a[i]<b[i]≤2；
对于 60%的数据，N≤50, -20≤a[i]<b[i]≤20；
对于 100%的数据，
N≤200，-25≤a[i]<b[i]≤25，1≤c[i]≤20，0≤d[i] ≤10000

/*
  这类似于一个多重背包的问题，给出n个物品，每个物品可以选a[i]到b[i]件，体积为c[i]，价值为d[i]， 然后问恰好填满一个容量为0的背包的最大价值。
  对于这个问题，我们可以把范围转换成0~b[i]-a[i]，那么选的件数就成了e[i]-a[i]，那么背包的体积就成了-a[i]*c[i]，价值是(e[i]-a[i])*d[i]+Σa[i]*d[i]。 
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 210
using namespace std;
int a[N],b[N],c[N],d[N],n,m;
int f[101000],w[3010],v[3010],num,ans;
void init(int ss,int ww,int vv)
{
    for(int i=1;i<=ss;i*=2)
    {
        w[++num]=ww*i;v[num]=vv*i;
        ss-=i;
    }
    if(ss){w[++num]=ss*ww;v[num]=ss*vv;}
}
int main()
{
    memset(f,-127/3,sizeof(f));f[0]=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
        b[i]-=a[i];ans+=a[i]*d[i];m-=a[i]*c[i];
    }
    for(int i=1;i<=n;i++)
      init(b[i],c[i],d[i]);
    for(int i=1;i<=num;i++)
      for(int j=m;j>=w[i];j--)
        f[j]=max(f[j-w[i]]+v[i],f[j]);
    printf("%d",f[m]+ans);
    return 0;
}