P1450 [HAOI2008]硬币购物 （多重背包，前缀和，半个单调队列？？？）

• 显然是个多重背包的问题（没看出来容斥的话），但这题只问我们 f [ s ] f[s] f[s] 的方案数，所以更简单（都不需要考虑价值了）

  恰巧我刚好学了用单调队列去优化，但是发现，与最值都没关系，我优化个寂寞

• 但是还是让我发现了一种神奇的解法，前缀和+半个单调队列，详见代码

• 时间复杂度 O ( n s ) O(ns) O(ns) , 刚好卡着过去了（(lll￢ω￢)）

#include 
using namespace std;

typedef long long ll;
const int N=1005,M=1e5+5;
int c[N],d[N];
ll f[M],pre[M],q[M],sum[M];
signed main()
{
    int n;
    scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&n);
    while(n--)
    {
        int s;
        scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&s);
        memset(f,0,sizeof(f));
        f[0]=1;
        for(int i=1;i<=4;i++)
        {
            memcpy(pre,f,sizeof(f));
            for(int j=0;jd[i]) l++;
                    f[k]+=sum[r]-sum[l];
                    r++;
                    sum[r]=sum[r-1]+pre[k];
                    //cout<