#include <bits/stdc++.h>
using namespace std;
long long n,m,v[15],dp[3005];
int main()
{
    scanf("%lld%lld",&n,&m);dp[0]=1;
    for(int i = 0;i < n;i++)scanf("%lld",&v[i]);
    for(int i = 0;i < n;i++)for(int j = v[i];j <= m;j++)dp[j]+=dp[j-v[i]];
    printf("%lld",dp[m]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,dp[2005],v[4]={10,20,50,100};
int main()
{
    scanf("%d",&n);dp[0]=1;
    for(int i = 0;i < 4;i++)for(int j = v[i];j <= n;j++)dp[j]+=dp[j-v[i]];
    printf("%d",dp[n]);
    return 0;
}

蒟蒻cz的题库

欢迎加入

#include <bits/stdc++.h>
using namespace std;
int n,m,a[105],dp[10005];
int main()
{
    scanf("%d%d",&n,&m);dp[0]=1;
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    for(int i = 1;i <= n;i++)for(int j = m;j >= a[i];j--)dp[j]+=dp[j-a[i]];
    printf("%d",dp[m]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m,k,v1,v2,dp[1005][505];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    while(k--)
    {
        scanf("%d%d",&v1,&v2);
        for(int i = n;i >= v1;i--)for(int j = m-1;j >= v2;j--)dp[i][j]=max(dp[i][j],dp[i-v1][j-v2]+1);
    }
    int x=m-1;
    while(x>0&&dp[n][x-1]==dp[n][m-1])x--;
    printf("%d %d",dp[n][m-1],m-x);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int v,n,a[35],dp[20005];
int main()
{
    scanf("%d%d",&v,&n);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    for(int i = 1;i <= n;i++)for(int j = v;j >= a[i];j--)dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
    printf("%d",v-dp[v]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int t,m,a[105],b[105],dp[1005];
int main()
{
    scanf("%d%d",&t,&m);
    for(int i = 1;i <= m;i++)scanf("%d%d",&a[i],&b[i]);
    for(int i = 1;i <= m;i++)for(int j = t;j >= a[i];j--)dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
    printf("%d",dp[t]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n=0,a[1005],dp[1005],s[1005],ans=INT_MIN;
int main()
{
    while(~scanf("%d",&a[++n]));n--;
    for(int i = 1;i <= n;i++)
    {
        dp[i]=1;
        for(int j = 1;j < i;j++)if(a[j]>=a[i])dp[i]=max(dp[i],dp[j]+1);
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);ans=0;
    for(int i = 1;i <= n;i++)
    {
        int k=0;
        while(k<ans&&s[k+1]<a[i])k++;
        s[k+1]=a[i];
        if(k==ans)ans++;
    }
    printf("%d",ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n=0,a[1005],dp[1005],s[1005],ans=INT_MIN;
int main()
{
    while(~scanf("%d",&a[++n]));n--;
    for(int i = 1;i <= n;i++)
    {
        dp[i]=1;
        for(int j = 1;j < i;j++)if(a[j]>=a[i])dp[i]=max(dp[i],dp[j]+1);
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);ans=0;
    for(int i = 1;i <= n;i++)
    {
        int k=0;
        while(k<ans&&s[k+1]<a[i])k++;
        s[k+1]=a[i];
        if(k==ans)ans++;
    }
    printf("%d",ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int a,b;
    bool operator<(const node T)
    {
        if(a!=T.a)return a<T.a;
        return b<T.b;
    }
}a[5005];
int n,ans=INT_MIN,dp[5005];
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%d%d",&a[i].a,&a[i].b);
    sort(a+1,a+n+1);
    for(int i = 1;i <= n;i++)
    {
        dp[i]=1;
        for(int j = 1;j < i;j++)if(a[i].b>a[j].b)dp[i]=max(dp[i],dp[j]+1);
        ans=max(ans,dp[i]);
    }
    printf("%d",ans);
    return 0;
}