ABCD
题目背景
SOURCE：NOIP2016-AHSDFZ T2
题目描述
有 4 个长度为 N 的数组 a，b，c，d 。现在需要你选择 N 个数构成数组e ，数组e 满足 a[i]≤e[i]≤b[i] 以及 
并且使得 
最大。
输入格式
输入文件共 N+1 行。
第 1 行包含 1 个正整数 N 。
第 i+1 行包含 4 个整数 a[i]，b[i]，c[i]，d[i] 。
输出格式
输出共 1 行，包含 1 个整数，表示所给出公式的最大值。输入数据保证一定有解。
样例数据 1
输入
5
-1 1 2 5
-2 2 1 2
0 1 1 3
-2 -1 3 10
-2 2 3 9
输出
2
样例数据 2
输入
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
输出
90
样例数据 3
输入
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
输出
-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] ≤100000。
好吧我承认这道题我又zz" role="presentation" style="position: relative;">zzzz了，考试时竟然爆0" role="presentation" style="position: relative;">00，唉下来之后发现就是个简单dp" role="presentation" style="position: relative;">dpdp。
我们对原来的限制条件变形，让0≤num[i]≤a[i]−b[i]" role="presentation" style="position: relative;">0≤num[i]≤a[i]−b[i]0≤num[i]≤a[i]−b[i]，然后令num[i]=e[i]−a[i]" role="presentation" style="position: relative;">num[i]=e[i]−a[i]num[i]=e[i]−a[i]，代入原来的式子运算，会发现这是一道背包。b[i]−a[i]" role="presentation" style="position: relative;">b[i]−a[i]b[i]−a[i]是物品的数量限制，num[i]" role="presentation" style="position: relative;">num[i]num[i]是物品i" role="presentation" style="position: relative;">ii的选取数量限制，c[i]" role="presentation" style="position: relative;">c[i]c[i]则是物品的大小，然后就是背包了。
然而我们发现，这样子只有60" role="presentation" style="position: relative;">6060分。因此需要用一个叫做单调队列的东西进行优化。代码如下：
#include<bits/stdc++.h>
#define N 210
#define M 100010
using namespace std;
int n,m,a[N],b[N],c[N],d[N],dp[M],ans,q[M],f[M],head,tail;
int main(){
scanf("%d",&n),ans=m=0;
for(int i=1;i<=n;++i){
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
b[i]-=a[i];
m-=a[i]*c[i];
ans+=a[i]*d[i];
}
memset(dp,128,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;++i)
for(int j=0;j<c[i];++j){
head=1,tail=0;
for(int k=j;k<=m;k+=c[i]){
if(head<=tail&&k-q[head]==(b[i]+1)*c[i])++head;
while(head<=tail&&f[tail]+(k-q[tail])/c[i]*d[i]<=dp[k])--tail;
q[++tail]=k,f[tail]=dp[k];
dp[k]=f[head]+(k-q[head])/c[i]*d[i];
}
}
printf("%d",ans+dp[m]);
return 0;
}