洛谷 225153 数字组合
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
1.数字组合
题目链接数字组合 - 洛谷
标签背包问题
注意点将dp[0]初始化为1
AC代码
#include<iostream>
using namespace std;
int dp[100005];
int main()
{
int n,m,t;
cin>>n>>m;
dp[0]=1;
for(int i=1;i<=n;++i)
{
cin>>t;
for(int j=m;j>0;j--)
{
if(j>=t) dp[j]+=dp[j-t];
}
}
cout<<dp[m]<<endl;
return 0;
}
2.何以包邮
AC代码
#include<iostream>
using namespace std;
const int MAXN = 300005;
int main()
{
int n,m;
int t;
bool f[MAXN];
cin>>n>>m;
f[0]=true;
for(int i=0;i<n;++i)
{
cin>>t;
for(int j=MAXN;j>=t;j--)
{
if(f[j-t]) f[j]=true;
}
}
for(int i=m;i<MAXN;i++)
{
if(f[i])
{
cout<<i<<endl;
break;
}
}
return 0;
}