Chapter 3 数学与简单DP
上取整：
a / b //下取整
(a + b - 1) / b //上取整
+++
-
数学
1.买不到的数目 1205
//如果不知道公式，可以暴搜打表找规律（★）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
bool dfs(int u, int n, int m)
{
if(!u) return true;
if(u >= n && dfs(u - n, n, m)) return true;
if(u >= m && dfs(u - m, n, m)) return true;
return false;
}
int main()
{
int n, m;
int res = 0;
cin >> n >> m;
for(int i = 0; i <= 1000; i++)
if(!dfs(i, n, m)) res = i;
cout << res << endl;
return 0;
}
/*打表
3 4 5
3 5 7
3 7 11
3 8 13
3 10 17
*/
AC code
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
cout << (n - 1) * (m - 1) - 1 << endl;//公式，记住
return 0;
}
2.蚂蚁感冒 1211
//脑筋急转弯，，换位思考
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 55;
int ant[maxn];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++ ) cin >> ant[i];
int left = 0, right = 0;
for(int i = 1; i < n; i++ )
{
if(abs(ant[i]) < abs(ant[0]) && ant[i] > 0) left ++;
if(abs(ant[i]) > abs(ant[0]) && ant[i] < 0) right ++;
}
if(ant[0] > 0 && right == 0 || ant[0] < 0 && left == 0) cout << 1 << endl;
else cout << left + right + 1 << endl;
return 0;
}
3.饮料换购 1216
//小学数学题
#include <iostream>
using namespace std;
int sum, m;
void dfs(int u)
{
if(u < 3) return;
sum += u / 3;
dfs(u / 3 + u % 3);
}
int main()
{
cin >> m;
sum = m;
dfs(m);
cout << sum << endl;
}
- 简单DP
1.状态表示 ： 数组元素 表示的是一个集合，存的当前集合的属性
i为行下标 j为列下标 表示只从前i个物品中选，物品总体积<= j
2.状态计算
集合的划分
1.01背包问题 2
//无优化版
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int f[maxn][maxn];//代表集合，存放符合需要的数据
int v[maxn], w[maxn];
int m, n;
int main()
{
cin >> m >> n;
for(int i = 1; i <= m; i++ ) cin >> v[i] >> w[i];
for(int i = 1; i <= m; i++ )
for(int j = 0; j <= n; j++ )
{
f[i][j] = f[i - 1][j];//不选第i个的情况
//选择第i个的情况
if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout <<f[m][n] << endl;
return 0;
}
//优化版本
/*
1. f[i] 仅用到了f[i-1]层,
2. j与j-v[i] 均小于j
3.若用到上一层的状态时,从大到小枚举, 反之从小到大
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int n, m;
int v[maxn], w[maxn];
int f[maxn];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++ ) cin >> v[i] >> w[i];
for(int i = 1; i <+ m; i++ )
for(int j = m; j >= v[i]; j--)//j从大到小
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
2.摘花生 1015
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 105;
int f[maxn][maxn], w[maxn][maxn];//f[][]为存放路线与路线最大值的二维数组
int m, n;
int T;
int main()
{
cin >> T;
while(T--)
{
scanf("%d%d", &m, &n);
for(int i = 1; i <= m; i++ )
for(int j = 1; j <= n; j++ )
scanf("%d", &w[i][j]);
for(int i = 1; i <= m; i++ )
for(int j = 1; j <= n; j++ )
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
//f[i][j]为上一步最大值加上w[i][j]的花生数目
cout << f[m][n] << endl;
}
return 0;
}
3.最长上升子序列 895
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int a[maxn], b[maxn];
int n, res;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++ )cin >> a[i];
for(int i = 1; i <= n; i++ )
{
b[i] = 1;
for(int j = 1; j < i; j++ )
if(a[j] < a[i]) b[i] = max(b[i], b[j] + 1);
res = max(res, b[i]);
}
cout << res << endl;
return 0;
}
4.地宫取宝 1212
这题是最大上升子序列加上摘花生的结合版本，要考虑的东西变多了。
1.要考虑每次拿的宝物的价值与最大上升子序列类似，只不过序列数是固定的
2.4维dp，i j k v 分别表示从起点走到坐标i j，捡起来了k件宝物，宝物的最大价值是v
3.起点的初始化问题
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 55, MOD = 1e9 + 7;
int w[maxn][maxn];
int f[maxn][maxn][13][14];
int n, m, k;
int main()
{
cin >> m >> n >> k;
for(int i = 1; i <= m; i++ )
for(int j = 1; j <= n; j++ )
{
scanf("%d", &w[i][j]);
w[i][j]++;
}
f[1][1][0][0] = 1;//初始化
f[1][1][1][w[1][1]] = 1;
for(int i = 1; i <= m; i++ )
for(int j = 1; j <= n; j++ )
{
if(i == 1 && j == 1) continue;//因为[1][1]已经初始化过，可无
for(int u = 0; u <= k; u++ )
for(int v = 0; v <= 13; v++ )
{
int &val = f[i][j][u][v];//引用使代码看起来简洁
//不选w[i][j]的两种情况
val = (val + f[i - 1][j][u][v]) % MOD;
val = (val + f[i][j - 1][u][v]) % MOD;
if(u > 0 && v == w[i][j])//选w[i][j]的两种情况
{
for(int c = 0; c < v; c++ )
{
val = (val + f[i - 1][j][u - 1][c]) % MOD;
val = (val + f[i][j - 1][u - 1][c]) % MOD;
}
}
}
}
int res = 0;
for(int v = 0; v <= 13; v ++ ) res = (res + f[m][n][k][v]) % MOD;
cout << res << endl;
return 0;
}
5.波动数列 1214
设第一项为x，di 为+a或者-b，则序列可以表示为：
x , x + d1, x + d1 + d2, ... , x + d(n-1)
则s = n * x + (n - 1)d1 + (n - 2)d2 + ... + d(n - 1)
因为x的取值范围为R，因此想到用其他变量表示x，而且方面起见，将d的序号反过来
x = [s - (d1 + 2d2 + 3d3 + ... + (n - 1)d(n - 1))] / n
首先可以知道一组合法的di序列对应一个唯一的x，所以题目问题也就是问有多少组合法的di序列
其次因为x是整数，所以又可以转换为有多少组di序列使得上式的分子mod n余数相等
//f[i][j]表示前i组di序列mod n的余数为j的序列数的总和
//设前i-1项mod n为c，则f[i][j]项mod n的值就是 c + i * a = j mod n,
//因此c为(j - a * i) mod n
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1010, MOD = 100000007;
int f[maxn][maxn];//第二维表示mod n为 j的序列和
int get_mod(int x, int y)//确保mod的余数全部为整数，防止数组越界
{
return (x % y + y) % y;
}
int main()
{
int n, s, a, b;
cin >> n >> s >> a >> b;
f[0][0] = 1;//初始化
for(int i = 1; i < n; i++ )
for(int j = 0; j < n; j ++ )
f[i][j] = (f[i - 1][get_mod(j - a * (n - i), n)] + f[i - 1][get_mod(j + b * (n - i), n)]) % MOD;
//最后要输出的是前n - 1 项序列和mod n的数值为 get_mod(s, n)的合法序列数目
cout << f[n - 1][get_mod(s, n)] << endl;
return 0;
}