cms那个做网站最好,怎么做音乐mp3下载网站,北京建设局网站,小程序开发公司谁知道【题目链接】活动 - AcWing 输入样例1#xff1a;
20输出样例1#xff1a;
2输入样例2#xff1a;
15输出样例2#xff1a;
0输入样例3#xff1a;
0输出样例3#xff1a;
1
【代码】
//1023.买书——完全背包问题#includebits/stdc.husing namespace st…【题目链接】活动 - AcWing 输入样例1
20输出样例1
2输入样例2
15输出样例2
0输入样例3
0输出样例3
1
【代码】
//1023.买书——完全背包问题#includebits/stdc.husing namespace std;int a[5]{0,10,20,50,100};int dp[5][1010];int main(){int n;cinn;dp[0][0]1;for(int i1;i4;i){for(int j0;jn;j){dp[i][j]dp[i-1][j];if(ja[i]) dp[i][j]dp[i][j-a[i]];} } coutdp[4][n];return 0;} 【完全背包优化后代码】
//优化后
//1023.买书——完全背包问题
#includebits/stdc.h
using namespace std;
int a[5]{0,10,20,50,100};
int dp[1010];
int main()
{int n;cinn;dp[0]1;for(int i1;i4;i){for(int ja[i];jn;j){dp[j]dp[j-a[i]];} } coutdp[n];return 0;
} 【相似题目——AcWing1371.货币系统】
【题目链接】 1371. 货币系统 - AcWing题库 输入样例
3 10
1 2 5输出样例
10 【代码及注释】
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N1e510;
ll dp[30][N];
int v[N];
int main()
{int n,m;cinnm;for(int i1;in;i){cinv[i]; }dp[0][0]1;for(int i1;in;i){for(int j0;jm;j){dp[i][j]dp[i-1][j];//不选择第i个物品if(jv[i]) dp[i][j]dp[i][j-v[i]]; }}coutdp[n][m];return 0;
}
【优化后代码】
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N1e510;
ll dp[N];
int v[N];
int main()
{int n,m;cinnm;for(int i1;in;i){cinv[i]; }dp[0]1;for(int i1;in;i){for(int jv[i];jm;j){dp[j]dp[j-v[i]]; }}coutdp[m];return 0;
}
