目录

• 🌟一、买不到的数目 [数学]
• • 思路 (数论)
  • AC代码
• 🌟二、蚂蚁感冒
• • 思路
  • AC代码
• 🌟三、饮料换购 [数学]
• • 思路
  • AC代码
• 🌟四、摘花生
• • 思路
  • AC代码
• 🌟五、最长上升子序列
• • 思路
  • AC代码
• 🌟六、地宫取宝
• • 思路
  • AC代码

前三道数学
后四道简单DP

🌟一、买不到的数目 [数学]

题目链接

题目描述小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买  10  颗糖。你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。输入两个正整数，表示每种包装中糖的颗数(都不多于1000) 输出一个正整数，表示最大不能买到的糖数 样例输入4 7 样例输出17

思路 (数论)

“公约数只有1的两个数，叫做互质数。”
d=gcd(a,b)>1,则一定不能凑出最大数
就是两个正整数直接本身没有倍数关系，且它们的因数之间也没有倍数关系（因数1除外）。比如13和27互质，13=113，27=39=1*27，13和3，9直接就没有倍数关系。又比如31和89，47和11等等… …
O(1)
y总的结论：如果 a,ba,b 均是正整数且互质，
那么由 ax+by,x≥0,y≥0ax+by,x≥0,y≥0
不难凑出的最大数是a*b - a - b

AC代码

#include  using namespace std;int a,b;int main () {cin >> a >> b;cout << a * b - a - b <<endl; return 0;} 

🌟二、蚂蚁感冒

题目描述长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。输入第一行输入一个整数n  (1  <   n  <   50),  表示蚂蚁的总数。 接着的一行是n个用空格分开的整数  Xi  (-100  <   Xi  <   100),  Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数  据代表的蚂蚁感冒了。输出要求输出1个整数，表示最后感冒蚂蚁的数目。 样例输入5-10 8 -20 12 25样例输出3

思路

• 当两只蚂蚁碰面时，它们同时掉头往相反的方向爬行就等价于两只蚂蚁相互穿过对方，由此不用管题目的掉头
• 分析情况：如图，
  

AC代码

#include using namespace std;const int N =55;int a[N];// + :右  - ：左 int main () {int n;cin >> n;for (int i =0; i < n; i ++) {cin >> a[i];}//右向左      左向右 蚂蚁的数量 int LeftToRight = 0, RightToLeft = 0;for (int i = 1; i < n; i ++) {//如果在感冒蚂蚁的右边 且 方向向左if (abs(a[i]) > abs(a[0]) && a[i] < 0) {RightToLeft ++;}//如果在感冒蚂蚁的左边 且 方向向右 else if (abs(a[i]) < abs(a[0]) && a[i] > 0) {LeftToRight ++;}}//感冒蚂蚁右 且有右向左的蚂蚁   冒蚂蚁左 且有右向左的蚂蚁 if((a[0] > 0 && RightToLeft) || (a[0] < 0 && LeftToRight)) {cout << LeftToRight + RightToLeft + 1 << endl; }else {cout << 1 << endl;}return 0;}

🌟三、饮料换购 [数学]

饮料换购题目乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料，凭3个瓶盖可以再换一瓶C型饮料，并且可以一直循环下去(但不允许暂借或赊账)。请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 n 瓶饮料，最后他一共能喝到多少瓶饮料。输入格式输入一个整数 n,表示初始买入的饮料数量。输出格式输出一个整数，表示一共能够喝到的饮料数量。数据范围0 < n < 10000 0<n<100000<n<10000输入样例100输出样例149

思路

就一水题，模拟即可

AC代码

#include using namespace std;int main ()  {int n,t = 0,ans;cin >> n;ans = n;while (n > 2) {  t = n / 3;//换购的 ans += t; n %= 3;//原来没换的 n += t;//换的  } cout << ans << endl;return 0;} 

🌟四、摘花生

思路

类似数字三角形

• 闫式DP ：状态表示划分依据是根据最后一步划分的！！！！！

AC代码

#include using namespace std;const int N = 110 , INF = 1e9;int f[N][N];//路线int w[N][N];//每个格子花生数int main () {  int n;  cin >> n;  while (n --) {    int h,l;//行列    cin >> h >> l;    for (int i = 1; i <= h; i ++ ) {      for (int j = 1; j <= l; j ++ ) { cin >> w[i][j];      }    }    f[1][1] = w[1][1];    for (int i = 1; i <= h; i ++) {//涉及i-1 保证数组从1开始 for (int j = 1; j <= l; j++) {     f[i][j] = max(f[i][j - 1], f[i - 1][j]) + w[i][j]; }    }    cout << f[h][l] << endl;  }  return 0;}

🌟五、最长上升子序列

题目链接

思路

双指针 + DP

AC代码

#include using namespace std;const int N = 1010;int f[N];int a[N];int main(){     int n,ans = 1; //最小是1 不能起负无穷    cin >> n;    for (int i = 1; i <= n; i ++) { cin >> a[i];    }    for (int i = 1; i <= n; i ++) { f[i] = 1; //初始化 只有a[i]一个  for (int j = 1; j < i; j ++) {    if (a[i] > a[j]) {  f[i] = max(f[i], f[j] + 1);    }  } ans = max(ans, f[i]);    }    cout << ans << endl;    return 0;}

🌟六、地宫取宝

题目链接

思路

计数DP + 摘花生

dalao的图

AC代码

//地宫寻宝//  第一个要想清楚的就是，要取得当前格子的物品，这个物品必须比当前所拥有的物品都大，所以有一个性质://  后面拿的物品比前面的物品大#include using namespace std;const int N = 55,M = 15,mod = 1000000007;int dp[N][N][M][M];//一二维表示行列  三维：件数  四维：价值 int w[N][N];long long res = 0;int main () {int n,m,k;//输入 cin >> n >> m >> k;for (int i = 1;i <= n; i ++ ) { //从1开始 for (int j = 1;j <=m; j ++) {cin >> w[i][j];w[i][j]++;//全加1 ,就变成了1到13,为了与其他方案区别，0就可以作为不选择的下标}}//初始化dp[1][1][0][0] = 1;//起始点不选 方案数 1dp[1][1][1][w[1][1]] = 1;//起始点选 方案数 1//枚举for(int i = 1; i <= n; i ++) {//枚举移动 for(int j = 1;j <= m; j ++) {for (int cnt = 0; cnt <= k; cnt ++) { //枚举拿物品的个数 for (int v = 0; v <= 13; v ++) { //枚举取到的最大物品的价值 上面全部+1 所以此处 为13 //不选 dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt][v]) % mod; dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt][v]) % mod; //选if(cnt > 0 && v == w[i][j]) {for (int s = 0; s < w[i][j]; s++) {dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt - 1][s]) % mod;dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt - 1][s]) % mod;}} }}}}//方案计数 int res = 0;for(int i = 1; i <= 13; i ++) {res= (res + dp[n][m][k][i]) % mod;}//输出 cout << res << endl;return 0;}