《动态规划C++NOIP信息学竞赛》由会员分享，可在线阅读，更多相关《动态规划C++NOIP信息学竞赛（17页珍藏版）》请在金锄头文库上搜索。
1、动态规划算法数字三角形背景 Background09 年 USACO 11月月赛 铜牌第一道 描述 Description示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路 径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走； 1三角形行数25；三角形中的数字为整数1000； 输入格式 Input Format第一行为N,表示有N行后面N行表示三角形每条路的路径权 输出格式 Output Format路径所经过的数字的总和最大的答案样例输入 Sample Input573 88 1 02 7 4 44 5 2 6 5 样例输出 Sample Output30时间
2、限制 Time Limitation 各个测试点 1s注释 Hint搜索 80 分,记忆化搜索 AC fi,j=max(fi+1,j,fi+1,j+1)+ai,j; #include#include#include #include using namespace std;int a3030,n;int main()cinn;for(int i=1;i=n;i+)for(int j=1;j=0;i-)for(int j=1;j=i;j+) aij+=max(ai+1j+1,ai+1j); couta11endl; return 0;机器分配描述 Description总公司拥有高效生产设备 M
3、 台，准备分给下属的 N 个公司。各分公司若获 得这些设备，可以为国家提供一定的盈利。问：如何分配这 M 台设备才能使国 家得到的盈利最大？求出最大盈利值。其中Mv=100, Nv=100。分配原则：每 个公司有权获得任意数目的设备，但总台数不得超过总设备数M。保存数据的 文件名从键盘输入。输入格式 Input Format第一行保存两个数，第一个数是公司数N，第二个数是设备数M。接下来是 一个N*M的矩阵，表明了第I个公司分配J台机器的盈利。输出格式 Output Format输出所有公司的最大利润和样例输入 Sample Input3 330 40 5020 30 5020 25 30样例
4、输出 Sample Output70时间限制 Time Limitation各个测试点1s注释 Hint最大利润是所有公司都分得一个机器所得到。公司可以不分机器保证所有的价值都是正整数，但valuei,1.m并不是单调的#include#include #include #include #include using namespace std; const int maxn = 105;int n,m,vmaxnmaxn,fmaxnmaxn;int main()cinnm;for(int i = 1;i = n;i+)for(int j = 1;j vij;for(int i = 1;i =
5、 n;i+)for(int j = 1;j = m;j+) for(int k = 0;k = j;k+) fij = max(fij,fi-1j-k + vik); coutfnm;return 0;采药http:/:8080/Problem_Show.asp?id=1005From silence背景 BackgroundNOIP2005 复赛普及组第三题描述 Description辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他 想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医 师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同
6、 的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时 间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可 以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 输入格式 Input Format输入文件 medic.in 的第一行有两个整数 T(1 = T = 1000)和 M(1 = M = 100),用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药 的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数， 分别表示采摘某株草药的时间和这株草药的价值。输出格式 Output Format输出文件 medi
7、c.out 包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。样例输入 Sample Input70 371 10069 11 2样例输出 Sample Output3时间限制 Time Limitation 各个测试点 1s注释 Hint对于30%的数据，M = 10；对于全部的数据，M = 100。include include using namespace std;struct nodeint time,weal;a194250;int f1942500,s=0,t,i,j,n;int main() cintn;for(i=1;iai.timeai.wea
8、l;for(i=1;i=n;i+) for(j=0;j=ai.time)fij=max(ai.weal+fi-1j-ai.time,fi-1j);else fij=fi-1j;coutfnt;return 0; 滑雪http:/:8080/Problem_Show.asp?id=1004From silence 背景 Background成成第一次模拟赛 第三道描述 Descriptiontrs 喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便， 我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须 向下倾斜。例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻
9、的点之一。例 如 24-17-16-1，其实 25-24-233-2-1 更长，事实上这是最长的一条。输入格式 Input Format 输入文件第1行：两个数字r，c(1v=r,cv=100)，表示矩阵的行列。第2.r+1行:每行c个数，表示这个矩阵。输出格式 Output Format 输出文件仅一行: 输出 1 个整数，表示可以滑行的最大长度。样例输入 Sample Input5 51234516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9样例输出 Sample Output25时间限制 Time Limitation各个测试点 1
10、s# include# include# include# include# includeusing namespace std;const int MAX_N = 100;int aMAX_N+8MAX_N+8;int visMAX_N+8MAX_N+8;int dis42 = 0,1,1,0,0,-1,-1,0;int r, c;int search( int x, int y )if ( visxy != -1 )return visxy;int t = 0;int nx, ny;for ( int i = 0;i 4;i+ )nx = x + disi0;ny = y + disi1
11、;if ( 0 = nx&nx r&0 = ny&ny anxny ) t = max( search( nx, ny ),t );return visxy = t+1;int main(void)memset(vis,-1,sizeof(vis);scanf(%d%d,&r,&c);for ( int i = 0;i r;i+ )for ( int j = 0;j aij;int max = 0;for ( int i = 0;i r;i+ )for ( int j = 0;j c;j+ )if ( max search( i,j )max = search( i, j );cout2-3-1 和 1-3-2-1，共 2 种。输入格式 Input Format输入文件 ball.in 共一行，有两个用空格隔开的整数n ，m(3=n=30，1=m=30)。输出格式 Output Format输出文件 ball.out 共一行，有一个整数，表示符合题意的方法数。样例输入 Sample Input3 3样例输出 Sample Output2时间限制 Time Limitation各个测试点 1s注释 Hint40%的数据满足：3v=nv=30, lv=mv=20100%的数据满足： 3=n=30， 1=m=30include include algor
