2/13 review Backpack + monotonic queue variant

Looking back on these backpacks and greed , It's much simpler ……qaq

ordinary 01 Knapsack for the number of solutions ：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e4+5;;
int v,n,a[30],f[maxn];

signed main()
{
    
    scanf("%lld%lld",&v,&n);
    for(int i=1;i<=v;i++)
        scanf("%lld",&a[i]);
    f[0]=1;
    for(int i=1;i<=v;i++)
    {
    
        for(int j=a[i];j<=n;j++)
            f[j]=f[j]+f[j-a[i]];
    }
    cout<<f[n]<<endl;
    return 0;
}

https://www.luogu.com.cn/problem/P1586
One more dimension is added ： Several numbers are used to form this result

f[i][j]: Representation number i It was used j The number makes up 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
const int M=32768;
int t,n,f[maxn][5];

signed main()
{
    
    f[0][0]=1;
    for(int i=1;i*i<=M;i++)
    {
    
        for(int j=i*i;j<=M;j++)
        {
    
            for(int k=1;k<=4;k++)
                f[j][k]+=f[j-i*i][k-1];
        }
    }
    scanf("%lld",&t);
    while(t--)
    {
    
        int n,tmp=0;
        scanf("%lld",&n);
        for(int i=1;i<=4;i++)
            tmp+=f[n][i];
        cout<<tmp<<endl;
    }
    return 0;
}

https://www.luogu.com.cn/problem/P1638
Constantly update the value of the left endpoint , If the last position of the left endpoint is greater than the left endpoint , be left++

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int pos[2005],p[maxn],n,m,k;

signed main()
{
    
    scanf("%lld%lld",&n,&m);
    memset(pos,-1,sizeof(pos));
    int l=1,ll=0,rr=0,ml=inf;
    for(int i=1;i<=n;i++)
    {
    
        scanf("%lld",&p[i]);
        if(pos[p[i]]==-1)
            k++;
        pos[p[i]]=i;
        while(l!=i&&l<pos[p[l]])
            l++;
        if(k==m&&i-l+1<ml)
        {
    
            ml=i-l+1;
            ll=l;
            rr=i;
        }
    }
    //cout<<ml<<endl;
    cout<<ll<<" "<<rr<<endl;
    return 0;
}