没有合适的资源?快使用搜索试试~ 我知道了~
动态规划-C++-NOIP-信息学竞赛.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 72 浏览量
2024-03-18
21:05:39
上传
评论
收藏 324KB PDF 举报
温馨提示
试读
17页
全国信息学奥林匹克联赛,计算机编程,论文,历届,信息技术比赛,参考资料,极具学习价值
资源推荐
资源详情
资源评论
动态规划算法
数字三角形
背景 Background
09 年 USACO 11 月月赛 铜牌第一道
描述 Description
示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径,使该路径所经过的数字的总和最大。
每一步可沿左斜线向下或右斜线向下走;
1<三角形行数<25;
三角形中的数字为整数<1000;
输入格式 Input Format
第一行为 N,表示有 N 行
后面 N 行表示三角形每条路的路径权
输出格式 Output Format
路径所经过的数字的总和最大的答案
样例输入 Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出 Sample Output
30
时间限制 Time Limitation
各个测试点 1s
注释 Hint
搜索 80 分,记忆化搜索 AC
f[i,j]=max(f[i+1,j],f[i+1,j+1])+a[i,j];
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[30][30],n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)scanf("%d",&a[i][j]);
for(int i=n-1;i>=0;i--)
{
for(int j=1;j<=i;j++)
{
a[i][j]+=max(a[i+1][j+1],a[i+1][j]);
}
}
cout<<a[1][1]<<endl;
return 0;
}
机器分配
描述 Description
总公司拥有高效生产设备 M 台,准备分给下属的 N 个公司。各分公司若获
得这些设备,可以为国家提供一定的盈利。问:如何分配这 M 台设备才能使国
家得到的盈利最大?求出最大盈利值。其中 M<=100,N<=100。分配原则:每
个公司有权获得任意数目的设备,但总台数不得超过总设备数 M。保存数据的
文件名从键盘输入。
输入格式 Input Format
第一行保存两个数,第一个数是公司数 N,第二个数是设备数 M。接下来是
一个 N*M 的矩阵,表明了第 I 个公司分配 J 台机器的盈利。
输出格式 Output Format
输出所有公司的最大利润和
样例输入 Sample Input
3 3
30 40 50
20 30 50
20 25 30
样例输出 Sample Output
70
时间限制 Time Limitation
各个测试点 1s
注释 Hint
最大利润是所有公司都分得一个机器所得到。
公司可以不分机器
保证所有的价值都是正整数,但 value[i,1..m]并不是单调的
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 105;
int n,m,v[maxn][maxn],f[maxn][maxn];
int main(){
cin>>n>>m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin>>v[i][j];
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
for(int k = 0;k <= j;k++){
f[i][j] = max(f[i][j],f[i-1][j-k] + v[i][k]);
}
}
}
cout<<f[n][m];
return 0;
}
采药
http://www.tyvj.cn:8080/Problem_Show.asp?id=1005
From silence
背景 Background
NOIP2005 复赛普及组第三题
描述 Description
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他
想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医
师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同
的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时
间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可
以让采到的草药的总价值最大。” 如果你是辰辰,你能完成这个任务吗?
输入格式 Input Format
输入文件 medic.in 的第一行有两个整数 T(1 <= T <= 1000)和 M(1 <= M
<= 100),用一个空格隔开,T 代表总共能够用来采药的时间,M 代表山洞里的
草药的数目。接下来的 M 行每行包括两个在 1 到 100 之间(包括 1 和 100)的
整数,分别表示采摘某株草药的时间和这株草药的价值。
输出格式 Output Format
输出文件 medic.out 包括一行,这一行只包含一个整数,表示在规定的时间内,
可以采到的草药的最大总价值。
样例输入 Sample Input
70 3
71 100
69 1
1 2
样例输出 Sample Output
3
时间限制 Time Limitation
各个测试点 1s
注释 Hint
对于 30%的数据,M <= 10;对于全部的数据,M <= 100。
include<cmath>
include<iostream>
using namespace std;
struct node{int time,weal;}a[194250];
int f[194][2500],s=0,t,i,j,n;
int main(){
cin>>t>>n;
for(i=1;i<=n;i++)cin>>a[i].time>>a[i].weal;
for(i=1;i<=n;i++)
for(j=0;j<=t;j++){
if(j>=a[i].time)f[i][j]=max(a[i].weal+f[i-1][j-a[i].time],f[i-1][j]);
else f[i][j]=f[i-1][j];
}
cout<<f[n][t];
return 0;
}
滑雪
http://www.tyvj.cn:8080/Problem_Show.asp?id=1004
From silence
背景 Background
成成第一次模拟赛 第三道
描述 Description
trs 喜欢滑雪。他来到了一个滑雪场,这个滑雪场是一个矩形,为了简便,
我们用 r 行 c 列的矩阵来表示每块地形。为了得到更快的速度,滑行的路线必须
向下倾斜。
例如样例中的那个矩形,可以从某个点滑向上下左右四个相邻的点之一。例
如 24-17-16-1,其实 25-24-23…3-2-1 更长,事实上这是最长的一条。
输入格式 Input Format
输入文件
第 1 行: 两个数字 r,c(1<=r,c<=100),表示矩阵的行列。
第 2..r+1 行:每行 c 个数,表示这个矩阵。
输出格式 Output Format
输出文件
仅一行: 输出 1 个整数,表示可以滑行的最大长度。
剩余16页未读,继续阅读
资源评论
阿拉伯梳子
- 粉丝: 1163
- 资源: 5391
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功