首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

D4——动态规划练习3、综合练习

  • 25-01-18 13:02
  • 2396
  • 12352
blog.csdn.net

题题题题

冰原狼

题目描述

冰原狼,也被称为黑狼,是特大而强大的狼。大部分的冰原狼来自德拉纳。狼群看起来像普通的狼,但这些生物的大小几乎是普通狼的两倍。这些强大的野兽有8 ~ 9英尺长,体重达到600 - 800磅,是最有名的兽人坐骑。这些大狼像人一样高,有着长长的颚骨,看起来好像可以咬断铁棒。他们有灼红的眼睛。冰原狼的皮毛有着斑驳的灰色或黑色的颜色。在卡利姆多北部地区和马尔戈尔,狼群茁壮成长。冰原狼狼群是非常高效的猎手,能够杀死他们捕获的任何东西。他们会在条件允许的时候,成群结队地包围并攻击敌人。
来自东方王国的冒险家马特,遇到一群可怕的冰原狼。有N匹狼站成一排(从左到右编号为1到N)。马特必须打败他们才能生存。一旦马特击败了一只可怕的狼,他将会遭受等同于当前这只狼的攻击值的伤害。而作为一群群居的野兽,每只狼i可以增加其相邻的狼bi的攻击。因此,每一个可怕的狼 i 的攻击值包括两个部分:其本身的基本攻击和来自相邻的狼的额外的攻击。增加的攻击值是暂时的,一旦当前这只狼被击败,它邻近的狼将不再从它得到额外的攻击值。然而,这两只狼(如果存在的话)当前就会彼此紧挨着。
例如,假设有3只冰原狼排成一排,它们的基本攻击分别是(3,5,7)。他们可以提供的额外攻击值 bi是 (8, 2, 0)。因此,它们目前的攻击值是(5、13、9)。如果马特先击败第二只狼,他将受到攻击值为13的伤害,活着的狼目前的攻击值就变成了(3,15)。
作为一个警觉和足智多谋的冒险家,马特可以决定他打败的冰原狼的顺序。因此,他想知道他打败所有的狼所必须遭受的最小伤害值是多少。

输入描述

第一行仅包含一个整数 T ,指示测试用例数。

对于每个测试用例,第一行仅包含一个整数 N(2 ≤ N ≤ 200)。

第二行包含 N 个整数ai (0 ≤  a i ≤ 100000),表示每只冰原狼的基本攻击值。
第三行包含 N 个整数 bi (0 ≤b i≤ 50000),表示每只冰原狼可以提供的额外攻击值。

输出描述

对于每个测试用例,输出一行"case #x:y",其中 x 是样例的编号(从 1 开始),y 是马特需要承担的最小伤害值。

样例

输入
2
3
3 5 7
8 2 0
10
1 3 5 7 9 2 4 6 8 10
9 4 1 2 1 2 1 4 5 1
输出
Case #1: 17
Case #2: 74

提示

在第一个样例中,马特从左到右打败了冰原狼。 他受到5 + 5 + 7 = 17点伤害,这是他必须承受的最少伤害。

代码

  1. #include
  2. #include
  3. #include
  4. #include
  5. using namespace std;
  6. int t,n,a[1005],b[1005],f[1005][1005],g=0;
  7. int main(){
  8. cin>>t;
  9. while(t--){
  10. cin>>n;
  11. g++;
  12. for(int i=1;i<=n;i++){
  13. cin>>a[i];
  14. }
  15. for(int i=1;i<=n;i++){
  16. cin>>b[i];
  17. }
  18. memset(f,0,sizeof f);
  19. b[0]=b[n+1]=0;
  20. for(int i=1;i<=n;i++){
  21. f[i][i]=a[i]+b[i-1]+b[i+1];
  22. }
  23. for(int l=1;l<=n;l++){
  24. for(int i=1;i<=n;i++){
  25. int j=i+l-1;
  26. f[i][j]=0x3f3f3f3f;
  27. for(int k=i;k<=j;k++){
  28. f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[k]+b[i-1]+b[j+1]);
  29. }
  30. }
  31. }
  32. cout<<"Case #"<": "<1][n]<<"\n";
  33. }
  34. return 0;
  35. }

自然数的拆分求方案数

题目类型:完全背包

题目描述

  给定一个自然数N,要求把N拆分成若干个正整数相加的形式,参与加法运算的数可以重复。注意:拆分方案不考虑顺序;至少拆分成2个数的和。   1≤N≤4000

求拆分的方案数 mod2147483648 的结果。

输入描述

  一个自然数N。  

输出描述

  输入一个整数,表示结果。  

样例

输入
7
输出
14

提示

1+1+1+1+1+1+1

1+1+1+1+1+2

1+1+1+1+3

1+1+1+2+2

1+1+1+4

1+1+2+3

1+1+5

1+2+2+2

1+2+4

1+3+3

1+6

2+2+3

2+5

3+4(共14行)

代码

  1. #include
  2. using namespace std;
  3. #define ll long long
  4. int n,f[40005];
  5. int main(){
  6. cin>>n;
  7. f[0]=1;
  8. for(int i=1;i
  9. for(int j=i;j<=n;j++){
  10. f[j]=f[j]+f[j-i];
  11. f[j]%=2147483648;
  12. }
  13. }
  14. cout<
  15. return 0;
  16. }

货币系统

题目描述

在网友的国度中共有 n 种不同面额的货币,第 i 种货币的面额为 a[i],你可以 假设每一种货币都有无穷多张。为了方便,我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。

在一个完善的货币系统中,每一个非负整数的金额 x 都应该可以被表示出,即对 每一个非负整数 x,都存在 n 个非负整数 t[i] 满足 a[i]× t[i] 的和为 x。然而, 在网友的国度中,货币系统可能是不完善的,即可能存在金额 x 不能被该货币系统表 示出。例如在货币系统 n=3, a=[2,5,9] 中,金额 1,3 就无法被表示出来。

两个货币系统 (n,a) 和 (m,b) 是等价的,当且仅当对于任意非负整数 x,它要 么均可以被两个货币系统表出,要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b),满足 (m,b) 与原来的货币系统 (n,a) 等价,且 m 尽可能的小。他们希望你来协助完成这 个艰巨的任务:找到最小的 m。

 

输入描述

输入文件名为 money.in。

输入文件的第一行包含一个整数 T,表示数据的组数。接下来按照如下格式分别给 出 T 组数据。

每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数 a[i]。

输出描述

输出文件名为 money.out。 

输出文件共有 T 行,对于每组数据,输出一行一个正整数,表示所有与 (n,a) 等 价的货币系统 (m,b) 中,最小的 m。

样例

输入
  1. 2
  2. 4
  3. 3 19 10 6
  4. 5
  5. 11 29 13 19 17
输出
  1. 2
  2. 5

提示

在第一组数据中,货币系统(2,[3,10])和给出的货币系统(n,a)等价,并可以验证不存在m<2的等价的货币系统,依次答案为2.

在第二组数据中,可以验证不存在m

对于 100% 的数据,满足 1 ≤ T ≤ 20,1≤n≤ 100,1≤ a[i] ≤ 25000。

代码

  1. #include
  2. #include
  3. using namespace std;
  4. #define ll long long
  5. int n,f[50005],t,a[105],maxx,ans;
  6. int main(){
  7. cin>>t;
  8. while(t--){
  9. cin>>n;
  10. memset(f,0,sizeof f);
  11. f[0]=1;
  12. maxx=0,ans=0;
  13. for(int i=1;i<=n;i++){
  14. cin>>a[i];
  15. maxx=max(a[i],maxx);
  16. }
  17. for(int i=1;i<=n;i++){
  18. for(int j=a[i];j<=maxx;j++){
  19. f[j]=f[j]+f[j-a[i]];
  20. }
  21. }
  22. for(int i=1;i<=n;i++){
  23. if(f[a[i]]==1){
  24. ans++;
  25. }
  26. }
  27. cout<"\n";
  28. }
  29. return 0;
  30. }

注:本文转载自blog.csdn.net的我是一个小太阳~~的文章"https://blog.csdn.net/XuyuxuanAa/article/details/145088888"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

137
数学
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top