abcd

【问题描述】
有4个长度为N的数组a,b,c,d。现在需要你选择N个数构成数组e，数组e满足a[i]≤e[i]≤b[i]以及Σ(i=1~n) e[i]*c[i]=0,
并且使得Σ(i=1~n) 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】
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】
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】
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]-a[i]是物品数量限制，num[i]是i物品的选取数量，c[i]是物品大小，SUM(-a[i]*c[i])是背包容量，d[i]是物品价值
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
int a[205],b[205],c[205],d[205],s[205];
int N,M,crt;
int F[2][100005];
il int gi()
{
    int x=0;
    short int t=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') t=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
int main()
{
    freopen("abcd.in","r",stdin);
    freopen("abcd.out","w",stdout);
    N=gi();
    for (int i=1;i<=N;i++)
    {
        a[i]=gi(),b[i]=gi(),c[i]=gi(),d[i]=gi();
        M-=a[i]*c[i];//求最小值
        crt+=a[i]*d[i];//最小的最大值
        s[i]=b[i]-a[i];//物品数量限制
    }
    for (int i=1;i<=M;i++)
        F[0][i]=-214748364;
    F[0][0]=0;//i代表当前算到第几个物品，j表示当前Σa[i]*c[i]的值，肯定是负数（要不然*c就达不到0）
    for (int i=1;i<=N;i++)
    {
        int x=i&1,y=(i-1)&1;//滚动
        for (int r=0;r<=c[i]-1;r++)//c[i]是物品大小
        {
            int q[100005]={},head=1,tail=0;//q模拟的是双向链表（递减）的功能
            for (int j=r;j<=M;j+=c[i])//起码装一个物品，但比容积要小
            {
                while (head<=tail && (j-q[head])/c[i]>s[i]) head++;//>代表它当前假定数量大于现有数量，扔掉
                while (head<=tail && F[y][j]-j/c[i]*d[i]>=F[y][q[tail]]-q[tail]/c[i]*d[i]) tail--;//单调队列维护单调性
                q[++tail]=j;//前面决策总比后面决策好
                F[x][j]=F[y][q[head]]-q[head]/c[i]*d[i]+j/c[i]*d[i];//弄掉max的DP，按此来说，q[head]存的是前面存物结果在当前情况下最优决策
            }
        }
    }
    printf("%d",crt+F[N&1][M]);//从这来看，F因代表能增长的最大值
    fclose(stdin);
    fclose(stdout);
    return 0;
}