分析：解法好神啊......
前50分可以通过背包dp加一些优化来得到.后面的数据因为询问太多，显然不能一个个处理.
一个神奇的做法：分治. 预处理出对于每一个点i,不考虑它 的答案f[i]. 只需要将它左边和右边的元素插入到背包中即可. 为了达到这一目的. 在分治的时候加一个判断：如果l == r - 1,则返回.这样可以保证不插入l这个点. 那么l的答案也就出来了.
插入背包可以用单调队列来优化.和单调队列优化多重背包差不多. 实现起来有点复杂，可以用vector来表示f数组.
注意：使用vector一定要初始化！并不是像数组那样能直接访问.
#include#include #include #include #include using namespace std;const int maxn = 1010;int n,a[maxn],b[maxn],c[maxn],q[maxn],Q;typedef vector vint;vint f[maxn];void modify(vint &v,int x){ vint temp(v); for (int i = 0; i < a[x]; i++) { int head = 0,tail = 0; for (int j = i; j < maxn; j += a[x]) { while (head < tail && temp[j] > temp[q[tail - 1]] + (j - q[tail - 1]) / a[x] * b[x]) tail--; q[tail++] = j; while (head < tail && (j - q[head]) / a[x] > c[x]) head++; v[j] = max(v[j],temp[q[head]] + (j - q[head]) / a[x] * b[x]); } }}void solve(int l,int r,const vint &d){ if (l + 1 == r) { f[l] = d; return; } int mid = (l + r) >> 1; vint dl(d),dr(d); for (int i = l; i < mid; i++) modify(dr,i); for (int i = mid; i < r; i++) modify(dl,i); solve(l,mid,dl); solve(mid,r,dr);}int main(){ scanf("%d",&n); for (int i = 0; i < n; i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); solve(0,n,vint(maxn,0)); scanf("%d",&Q); while (Q--) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",f[x][y]); } return 0;}