文章目录

01背包

1、按摩师

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

示例 1：

输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

示例 3：

输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

#include<cstdio>
#define _for(i,a,b) for(int i=a; i<b; i++)
using namespace std;
int a[99];
int dp[99]={0};
inline int max(int a, int b) {
  return a>b?a:b;
}
int getT(int size, int *p){
  if(size==0) return 0;
  if(size==1) return p[0];
  dp[0] = p[0];
  dp[1] = max(p[0],p[1]);
  _for(i,2,size){
    //遍历迄今为止的最大值，两种情况取较大：
        //1：预约本次，则上一次不预约（dp[i-2] + nums[i]）
       //2：本次不预约，则值为预约到上一次的最大值
    dp[i] = max(dp[i-1], dp[i-2]+p[i]);
  }
  return dp[size-1];
}
int main(){
  int n; scanf("%d",&n);
  _for(i,0,n) scanf("%d", &a[i]);
  printf("%d\r\n",getT(n,a)); 
  return 0;
}

2、蓝桥——天天向上

问题描述

A同学的学习成绩十分不稳定，于是老师对他说：“只要你连续4天成绩有进步，那我就奖励给你一朵小红花。”可是这对于A同学太困难了。于是，老师对他放宽了要求：“只要你有4天成绩是递增的，我就奖励你一朵小红花。”即只要对于第i、j、k、l四天，满足i<j<k<l并且对于成绩wi<wj<wk<wl，那么就可以得到一朵小红花的奖励。现让你求出，A同学可以得到多少朵小红花。

输入格式

第一行一个整数n，表示总共有n天。第二行n个数，表示每天的成绩wi。

输出格式

一个数，表示总共可以得到多少朵小红花。

样例输入

6

1 3 2 3 4 5

样例输出

6

数据规模和约定

对于40%的数据，n<=50；

　　对于100%的数据，n<=2000，0<=wi<=109。

#include<iostream>
#include<algorithm>
#define _for(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define maxSize 2005
using namespace std;
ll arr[maxSize] = {0};
ll dp[maxSize][4];
ll t;
ll ans;
ll dfs(int index, int depth){
  ll total = 0;
  if(depth==3){
    return 1;
  }
  if(dp[index][depth]!=0){
    return dp[index][depth];
  }
  _for(i,index+1, t){
    if(arr[index]<arr[i]){
      total+=dfs(i,depth+1); 
    }
  }
  dp[index][depth] = total;
  return total; 
} 
int main(){
  cin>>t;
  _for(i,0,t) cin>>arr[i];
  _for(i,0,t) ans+=dfs(i,0);
  cout<<ans<<endl;
  return 0;
}

3、传纸条

问题描述

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

　　在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

　　还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。

输入格式

输入第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。

　　接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。

输出格式

输出一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

样例输入

3 3

0 3 9

2 8 5

5 7 0

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MAXN 51
int matrix[MAXN][MAXN];
int d[2][MAXN][MAXN];
int MaxSum(int m, int n)
{
  memset(d, 0, sizeof(d));
  int i, j, k, x, y;
  for (k = m+n-3; k > 0; k--)
  {
    for (i = 0, j = k; i < m-1; i++, j--)
    {
      if (j >= n)
      {
        continue;
      }
      for (x = i+1, y = j-1; x < m; x++, y--)
      {
        d[k%2][i][x] = matrix[i][j] + matrix[x][y];
        int r = (k+1) % 2;
        d[k%2][i][x] +=
          MAX(MAX(d[r][i][x], d[r][i][x+1]), MAX(d[r][i+1][x], d[r][i+1][x+1]));
      }
    }
  }
  return d[1][0][1];
}
int main(void)
{
  int ncases;
  scanf("%d", &ncases);
  while (ncases-- != 0)
  {
    int m, n;
    scanf("%d%d", &m, &n);
    memset(matrix, 0, sizeof(matrix));
    int i, j;
    for (i = 0; i < m; i++)
    {
      for (j = 0; j < n; j++)
      {
        scanf("%d", &matrix[i][j]);
      }
    }
    printf("%d\n", MaxSum(m, n));
  }
  return 0;
}
/*
4 4
0 3 9 4
2 8 5 7
5 7 3 3
5 6 2 0
*/

5、加分二叉树

设一个 n个节点的二叉树 tree 的中序遍历为(1,2,3,…,n)，其中数字 1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第 i个节点的分数为 d_id，tree 及它的每个子树都有一个加分，任一棵子树subtree（也包含 tree 本身）的加分计算方法如下：

subtree 的左子树的加分 × subtree 的右子树的加分 + subtree 的根的分数。

若某个子树为空，规定其加分为 11，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为 (1,2,3,…,n) 且加分最高的二叉树 tree。要求输出

tree 的最高加分。
tree 的前序遍历。

输入格式

第 11 行 11 个整数 nn，为节点个数。

第 22 行 n个用空格隔开的整数，为每个节点的分数

输出格式

第 11 行 11 个整数，为最高加分

第 22 行 nn 个用空格隔开的整数，为该树的前序遍历。

输入输出样例

输入 #1复制

5
5 7 1 2 10

输出 #1复制

145
3 1 2 4 5

说明/提示

n< 30n<30。

分数 <100<100。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
int n,a[40], root[40][40];
ll dp[40][40];
// 深搜 
ll dfs(int L, int R){
  if(L>R) return 1;
  if(dp[L][R]) return dp[L][R];
  ll maxn = 0;
  for(int i=L; i<=R; i++){
    ll t= dfs(L, i-1) * dfs(i+1, R) + a[i];
    if(t>maxn){
      maxn = t;
      root[L][R] = i;
    }
  }
  return dp[L][R]=maxn;
}
// 先序遍历输出二叉树 
void dg(int L, int R){
  if(L>R) return;
  printf("%d ",root[L][R]);
  dg(L,root[L][R]-1);
  dg(root[L][R]+1, R);
}
int main(){
  scanf("%d",&n);
  for(int i=1; i<=n; i++){
    // 输入中序的二叉树
    scanf("%d",a+i);
    // 最大加分初始化 
    dp[i][i] = a[i];
    // 根节点初始化 
    root[i][i] = i;
  }
  printf("%lld\n",dfs(1,n));
  dg(1,n);
  return 0;
}

6、采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例输入

70 3

71 100

69 1

1 2

样例输出

3

分析：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JiIafcZ9-1619284399477)(.\pics\image-20210323154022994.png)]

#include<bits/stdc++.h>
using namespace std;
int m,t, w[105], v[105],dp[1005];
int main()
{
  cin>>t>>m;
  for(int i=1; i<=m; i++){
    cin>>w[i]>>v[i];
  }
  for(int i=1; i<=m; i++){
    for(int j=t; j>=w[i]; j--){
       dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
  }
  cout<<dp[t]<<endl;
  return 0;
}

7、开心的金明

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为55等：用整数1-51−5表示，第55等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过NN元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为22个正整数，用一个空格隔开：n,m（其中N(<30000)表示总钱数，m(<25)为希望购买物品的个数。）从第22行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有22个非负整数v p（其中vv表示该物品的价格(v \le 10000)(v≤10000)，p表示该物品的重要度(1-5)

输出格式

11个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)

输入输出样例

输入 #1复制

输出 #1复制

#include<bits/stdc++.h>
using namespace std;
const int maxn = 30;
int m,n, w[maxn], v[maxn],dp[30005]={0};
int main()
{
  // n是总钱数 
  cin >> n >>m;
  // m种物品 
  for(int i=1; i<=m; i++){
    cin>>w[i]>>v[i];
    v[i] = w[i]*v[i];
  }
  for(int i=1; i<=m; i++){
    for(int j=n; j>=w[i]; j--){
       dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
  }
  cout<<dp[n]<<endl;
  return 0;
}

8、装箱问题

题目描述

有一个箱子容量为V，同时有nn个物品（0<n≤30），每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

1个整数，表示箱子容量

1个整数，表示有n个物品

接下来n行，分别表示这n个物品的各自体积

输出格式

11个整数，表示箱子剩余空间。

输入输出样例

输入 #1复制

输出 #1复制

#include<bits/stdc++.h>
using namespace std;
const int maxn = 30;
int m,n, w[maxn],dp[20005]={0};
int main()
{
  // n是箱子容量 
  cin >> n >>m;
  // m种物品 
  for(int i=1; i<=m; i++){
    cin>>w[i];
  }
  for(int i=1; i<=m; i++){
    for(int j=n; j>=w[i]; j--){
      // 选还是不选 
       dp[j] = max(dp[j], dp[j-w[i]] + w[i]);
       // 剪枝 
       if(dp[j]==n){
        cout<<0;
        return 0;
       } 
    }
  }
  cout<<n-dp[n]<<endl;
  return 0;
}

9、小A 点菜(求方案数)

题目背景

uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。

uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩M元（M<=10000）。

餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i种卖ai元（ai<=1000）。由于是很低端的餐馆，所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”，所以他点单一定刚好吧uim身上所有钱花完。他想知道有多少种点菜方法。

由于小A肚子太饿，所以最多只能等待1秒。

输入输出格式

输入格式：

第一行是两个数字，表示N和M。

第二行起N个正数ai（可以有相同的数字，每个数字均在1000以内）。

输出格式：

一个正整数，表示点菜方案数。

输入输出样例

输入样例#1：

4 4

1 1 2 2

输出样例#1：

3

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int m,n, w[maxn],dp[20005]={1};
int main()
{
  // n是种类 
  cin >> n >>m;
  // m钱 
  for(int i=1; i<=n; i++){
    cin>>w[i];
  }
  for(int i=1; i<=n; i++){
    for(int j=m; j>=w[i]; j--){
      dp[j]  +=  dp[j-w[i]];
    }
  }
  cout<<dp[m]<<endl;
  return 0;
}

10、最大公约数

题目描述

选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入格式

输入一个正整数S。

输出格式

输出最大的约数之和。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

样例说明

取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。

数据规模

S<=1000

#include<bits/stdc++.h>
using namespace std;
int dp[1005], w[1005], v[1005];
int main()
{
  int n,m;
  scanf("%d",&n);
  m=n;
  for(int i=1; i<=n; i++){
    for(int j=1; j<i; j++){
      if(i%j==0){
        v[i]+=j;
      }
    }
  }
  for(int i=1; i<=n; i++){
    w[i]=i;
    for(int j=m; j>=w[i]; j-- ){
      dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
    }
  }
  printf("%d\n",dp[m]);
  return 0;
 }

11、精卫填海

题目描述

【版权说明】

本题为改编题。

【问题描述】

发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？

事实上，东海未填平的区域还需要至少体积为v的木石才可以填平，而西山上的木石还剩下n块，每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为c。

输入格式

输入文件的第一行是三个整数：v、n、c。

从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式

输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出’Impossible’（不带引号）。

输入输出样例

输入 #1复制

100 2 10
50 5
50 5

输出 #1复制

输入 #2复制

10 2 1
50 5
10 2

输出 #2复制

Impossible

说明/提示

【数据范围】

对于20%的数据，0<n<=50。

对于50%的数据，0<n<=1000。

对于100%的数据，0<n<=10000，所有读入的数均属于[0,10000]，最后结果<=c。

#include<bits/stdc++.h>
using namespace std;
int n, c,nv, v[10010], w[10010], dp[10010];
int main()
{
  // 还需要至少体积为nv的木石才可以填平
  // n块石头 c点体力 
  scanf("%d %d %d", &nv, &n, &c);
  for(int i=1; i<=n; i++){
    // 每块石头的体积 需要的体力 
    scanf("%d %d", &w[i],&v[i]);
  }
  // 规划n块石头选不选 
  for(int i=1; i<= n; i++)
  //要不要选当前的石头 
    for(int j=c; j>=v[i]; j--){
      dp[j] = max(dp[j], dp[j-v[i]]+w[i]);
    }
for(int i=0; i<=c; i++)
  if(dp[i]>=nv) {
    printf("%d",c-i);
    return 0;
  }
  printf("Impossible");
  return  0;
}

12、集合 Subset Sums

题目描述

对于从 1\sim n1∼n 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果 n=3n=3，对于 {1,2,3}{1,2,3} 能划分成两个子集合，每个子集合的所有数字和是相等的：

{3}{3} 和 {1,2}{1,2} 是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）

如果 n=7n=7，有四种方法能划分集合 {1,2,3,4,5,6,7 }{1,2,3,4,5,6,7}，每一种分法的子集合各数字和是相等的:

{1,6,7}{1,6,7} 和 {2,3,4,5}{2,3,4,5}

{2,5,7}{2,5,7} 和 {1,3,4,6}{1,3,4,6}

{3,4,7}{3,4,7} 和 {1,2,5,6}{1,2,5,6}

{1,2,4,7}{1,2,4,7} 和 {3,5,6}{3,5,6}

给出 nn，你的程序应该输出划分方案总数。

输入格式

输入文件只有一行，且只有一个整数 nn

输出格式

输出划分方案总数。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

【数据范围】

对于 100% 的数据，1≤n≤39。

翻译来自NOCOW

USACO 2.2

#include<bits/stdc++.h>
using namespace std;
int n;
long long dp[800] = {1};
int main()
{
  cin>>n;
  int m = n*(n+1)/2;
  if(m%2==1){
    cout<<0<<endl;
    return 0;
  } 
  for(int i=1; i<=n; i++){
    for(int j=m/2; j>=i; j--){
      dp[j] = dp[j] + dp[j-i];
    }
  }
  for(int i=1; i<=m/2; i++) cout<<dp[i]<<' ';
  cout<<endl;
  cout<<dp[m/2]/2<<endl;
  return 0;
}

13、超级玛丽

完全背包

1、疯狂采药

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NrEBBNPl-1619284399481)(.\pics\image-20210330161322760.png)]

输入输出样例

输入 #1复制

输出 #1复制

#include<bits/stdc++.h>
using namespace std;
long long n,m, dp[10000015], c[10000015], v[10000015];
int main()
{
  cin>>m>>n;
  for(int i=1; i<=n; i++){
    cin>>c[i]>>v[i];
  }
  for(int i=1; i<=n; i++){
    for(int j=c[i]; j<=m; j++){
      dp[j] = max(dp[j], dp[j-c[i]]+v[i]);
    }
  }
  cout<<dp[m]<<endl;
  return 0;
}

2、神奇的四次方数

题目描述

在你的帮助下，v神终于帮同学找到了最合适的大学，接下来就要通知同学了。在班级里负责联络网的是dm同学，于是v神便找到了dm同学，可dm同学正在忙于研究一道有趣的数学题，为了请dm出山，v神只好请你帮忙解决这道题了。

将一个整数m分解为n个四次方数的和的形式，要求n最小。例如，m=706,706=54+34,则n=2。

输入输出格式

输入格式：

一行，一个整数m。

输出格式：

一行，一个整数n。

输入输出样例

输入样例#1：

706

输出样例#1：

2

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, dp[N], c[110];
int main()
{
  memset(dp,63,sizeof(dp)); 
  dp[0] = 0;
  // 背包的容量 
  cin>>m;
  for(int i=1; i*i*i*i <= m; i++){
    c[i] = i*i*i*i;
    n = i;
  }
  for(int i=1; i<=n ;i++){
    for(int j=c[i]; j<=m; j++){
      dp[j] = min(dp[j], dp[j-c[i]]+1);
    }
  }
  cout<<dp[m];
  return 0;
}

3、通天之分组背包

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AejrP1Ow-1619284399486)(.\pics\image-20210407005427068.png)]

输入输出样例

输入 #1复制

输出 #1复制

DP

文章目录

01背包

1、按摩师

2、蓝桥——天天向上

3、传纸条

5、加分二叉树

6、采药

分析：

7、开心的金明

8、装箱问题

9、小A 点菜(求方案数)

10、最大公约数

题目描述

输入输出样例

说明/提示

11、精卫填海

题目描述

输入格式

输出格式

输入输出样例

说明/提示

12、集合 Subset Sums

题目描述

输入格式

输出格式

输入输出样例

说明/提示

13、超级玛丽

完全背包

1、疯狂采药

2、神奇的四次方数

3、通天之分组背包

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

DP

文章目录

01背包

1、按摩师

2、蓝桥——天天向上

3、传纸条

5、加分二叉树

6、采药

分析：

7、开心的金明

8、装箱问题

9、小A 点菜(求方案数)

10、最大公约数

题目描述

输入输出样例

说明/提示

11、精卫填海

题目描述

输入格式

输出格式

输入输出样例

说明/提示

12、集合 Subset Sums

题目描述

输入格式

输出格式

输入输出样例

说明/提示

13、超级玛丽

完全背包

1、疯狂采药

2、神奇的四次方数

3、通天之分组背包

热门文章

最新文章

相关电子书