luogu 2371 墨墨的等式

1.背包dp

#include<bits/stdc++.h>

#define rep(i,x,y) for(register int i=x;i<=y;i++)

#define ll long long

using namespace std;

const int N=;

const int M=1e6+;

int a[N],n,bmin,bmax;

inline int read(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;}

ll f[M];int ans;

int main(){

    scanf("%d%d%d",&n,&bmin,&bmax);

    rep(i,,n) a[i]=read();

    for(int i=;i<=n;i++)

    for(int j=a[i];j<=bmax;j++)

    f[j]=max(f[j],f[j-a[i]]+a[i]);

    for(int i=bmin;i<=bmax;i++)if(f[i]==i) ++ans;

    printf("%d\n",ans);return ;

}

2.最短路  啊啊啊搬了别人的代码，以后自己再写吧

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

#define ll long long

#define INF 0x3f3f3f3f3f3f3f3f

#define N 500100

using namespace std;

ll n,l,r,num[],d[N],ans;

bool in[N];

queue<ll>que;

int main()

{

    ll i,j,p,q;

    cin>>n>>l>>r;

    for(i=; i<=n; i++)

    {

        scanf("%lld",&num[i]);

    }

    sort(num+,num+n+);

    memset(d,0x3f,sizeof(d));

    d[]=;

    que.push();

    for(; !que.empty();)

    {

        p=que.front();

        que.pop();

        in[p]=;

        for(i=; i<=n; i++)

        {

            q=(p+num[i])%num[];

            if(d[q]<=d[p]+num[i]) continue;

            d[q]=d[p]+num[i];

            if(!in[q])

            {

                in[q]=;

                que.push(q);

            }

        }

    }

    for(i=,l--; i<num[]; i++)

    {

        if(d[i]>r) continue;

        if(d[i]<=l) ans+=(r-i)/num[]-(l-i)/num[];

        else ans+=(r-d[i])/num[]+;

    }

    cout<<ans;

}