题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
#include <iostream>
using namespace std;
const int N = 1010;
int f[5][N];
int v[5] ={0, 10, 20, 50, 100};//存储每种书的价格
int main()
{
int m;
cin >> m;
f[0][0] = 1;//从前零本数选择,价格为零的书是的方案为1
for(int i = 1; i <= 4; i ++)//从1~n遍历每本书
for(int j = 0; j <= m; j ++)//手上的钱0~m
{
//f[i][j]从前i本书选择,价格为j的法案数是多少等价于
//不选第i本书价值为j和选了第i本书价值为j的方案之和
f[i][j] = f[i - 1][j];
//优化前
//f[i][j] = max(f[i - 1][j], f[i - 1][j -v] + f[i - 1][j - 2 * v]……f[i - 1][j - s * v])
//f[i][j - v]= max( f[i -1][j -v] + f[i - 1][j - 2 * v]……f[i - 1][j - s * v])
//优化后
//f[i][j] = max(f[i - 1][j], f[i][j - v])
if(j >= v[i])f[i][j] += f[i][j - v[i]];
}
cout << f[4][m] << endl;
return 0;
}
C++ 代码
#include <iostream>
using namespace std;
const int N = 1010;
int f[5][N];
int v[5] ={0, 10, 20, 50, 100};//存储每种书的价格
int main()
{
int m;
cin >> m;
f[0][0] = 1;//从前零本数选择,价格为零的书是的方案为1
for(int i = 1; i <= 4; i ++)//从1~n遍历每本书
for(int j = 0; j <= m; j ++)//手上的钱0~m
{
//f[i][j]从前i本书选择,价格为j的法案数是多少等价于
//不选第i本书价值为j和选了第i本书价值为j的方案之和
f[i][j] = f[i - 1][j];
//优化前
//f[i][j] = max(f[i - 1][j], f[i - 1][j -v] + f[i - 1][j - 2 * v]……f[i - 1][j - s * v])
//f[i][j - v]= max( f[i -1][j -v] + f[i - 1][j - 2 * v]……f[i - 1][j - s * v])
//优化后
//f[i][j] = max(f[i - 1][j], f[i][j - v])
if(j >= v[i])f[i][j] += f[i][j - v[i]];
}
cout << f[4][m] << endl;
return 0;
}