北航DP问题整理.docx
- 文档编号:9244013
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:53
- 大小:47.60KB
北航DP问题整理.docx
《北航DP问题整理.docx》由会员分享,可在线阅读,更多相关《北航DP问题整理.docx(53页珍藏版)》请在冰点文库上搜索。
北航DP问题整理
DP问题整理:
祭祀广场
时间限制:
5000ms 内存限制:
16384KB
总提交:
1262(334users) 正确提交:
358(247users)
描述
古老的滕格森部落,生活在一片稀疏的树林之中,他们信仰伟大的长天昊大神。
一天晚上,部落的首领猛格做了一个梦里,在梦里得到了长天昊神的神谕,要求他的部落建立一个大型的广场,用来举行对长天昊大神的祭拜仪式。
其实,对于那时候的人来说,祭拜仪式之后常常会举行集体歌舞、狂欢活动,属于那个时代的群众娱乐项目。
腾格森部落生活的地方是一片乐土,环境优美,植物茂盛,动物成群,猛兽也不多。
虽然那时的人寿命并不长,但由于他们不实行计划生育,所以人口众多。
为了表示对长天昊大神的敬畏,同时也为了活动场地能容纳尽可能多的人,部落首领猛格想把广场建得越大越好。
根据神谕,广场必须是正方形。
但建设广场的那片区域,有一些古树、清泉和神迹,不能被破坏。
但腾格森部落的绘图术比较落后,他们把矩形区域分成一格一格,地图上可用来建设广场的地方标0,有古树和神迹的地方标1,整个地图就是一个1、0矩阵。
猛格把确定建设广场地址的任务交给了你,希望你能告诉他,广场到底能建多大。
输入
输入包含多组测试数据,每组测试数据的第一行是两个正整数M、N(1<=M<=3000,1<=N<=3000),表示建设广场的矩形区域的长和宽。
然后接下来是M×N的0、1矩阵。
输入数据以00结束。
输出
对应每组测试数据,仅输出一行,即广场的最大边长。
样例输入
3 4
0 1 0 0
0 0 0 0
1 0 0 1
5 5
0 0 0 1 0
0 0 0 0 0
1 1 0 0 0
0 0 0 0 0
1 0 0 0 1
0 0
样例输出
2
3
问题来源
BUAACampus2007
#include
usingnamespacestd;
inta[3000][3000];
intmin(inta,intb,intc){
if(a
return(a a: c; } else{ return(b b: c; } } intmain(){ intm,n; boolin; cin>>m>>n; while(m! =0||n! =0){ for(inti=0;i for(intj=0;j cin>>in; if(in){ a[i][j]=0; } else{ a[i][j]=1; } } }/* for(inti=1;i if(a[i][0]! =0){ a[i][0]+=a[i-1][0]; } } for(inti=1;i if(a[0][i]! =0){ a[0][i]+=a[0][i-1]; } }*/ for(inti=1;i for(intj=1;j if(a[i][j]! =0){ a[i][j]+=min(a[i-1][j],a[i-1][j-1],a[i][j-1]); } } } intbiggest=a[0][0]; for(inti=0;i for(intj=0;j if(a[i][j]>biggest){ biggest=a[i][j]; } } } cout< cin>>m>>n; } return0; } 防盗门系统 时间限制: 1000ms 内存限制: 65536KB 总提交: 560(186users) 正确提交: 204(152users) 描述 为了加强管理,北航ACM训练队准备在实验室安装“条形码防盗门系统”,防盗门识别到队员们证件上的条形码就能打开。 但是防盗门上的识别器模糊,Oyster曾经拿着一本《算法导论》的条形码溜进去了。 纸是包不住火的,这天刚好让队长LEO发现了,立刻下令: 我们要对所有的条形码进行测试! 条形码由许多粗细不同的黑白平行直线段夹并而成,现在我们要把它看成是许多粗细相同的直线段夹并成的(即,一根粗线看成几根单位粗的细线夹成)。 影响防盗门的识别器工作的主要原因是条形码之间的相似度太高。 从两个条形码各取若干部分(起始位置不必相同),分别夹并成两个新的“子条形码”,如果这两子条形码完全一致,那么它们是相似的,相似度就是两个条形码的最长的相似子条形码的长度。 输入 输入包括多组数据,第一行为一个整数T,表示数据的组数。 以下对应每个数据都有两行,分别为两个条形码的描述,其中0表示单位长度的白线,1表示单位长度的黑线,以换行符为行结束标志(长度不超过3200)。 (如上图为101110) 输出 对应每一组数据,只需要输出一行,它们的相似度L。 样例输入 2 10100 00 111000 1010 样例输出 2 3 提示 1、条形码按输入给出的方向计算,不需要倒置或翻转。 2、样例的最长子条形码分别为00和110。 #include #include main() { intt,i,al,bl,j; charaa[3201],bb[3201]; chara[3201],b[3201]; intf[2][3201]; scanf("%d",&t); getchar(); while(t--) { scanf("%s",&aa); scanf("%s",&bb); al=strlen(aa); bl=strlen(bb); for(i=al-1;i>=0;i--) a[i+1]=aa[i]; for(i=bl-1;i>=0;i--) b[i+1]=bb[i]; for(i=0;i<3201;i++) f[0][i]=0; f[1][0]=0; for(i=1;i<=bl;i++) for(j=1;j<=al;j++) { if(a[j]==b[i]) f[i%2][j]=f[(i-1)%2][j-1]+1; elseif(f[(i-1)%2][j]>f[i%2][j-1]) f[i%2][j]=f[(i-1)%2][j]; else f[i%2][j]=f[i%2][j-1]; } if(f[0][al]>f[1][al]) f[1][al]=f[0][al]; printf("%d\n",f[1][al]); } U盘测试 时间限制: 5000ms 内存限制: 65536KB 总提交: 220(38users) 正确提交: 73(22users) 描述 你知道吗? 一个质检及格的U盘从10层楼高处自由落体到地并不会带来任何数据损失! 而一个质检及格的ACM牌U盘,采用北航最尖端的RP材料技术,结构上符合RP守恒定律,从100层高楼自由落体到地可以毫发无伤! 这天,突然来了一位火星人,他说想在火星上测试一下这种ACM牌U盘是否能通过H层高楼的自由落体测试,你需要具体测出在哪一层U盘会摔坏(即在第P层测试会摔坏,在P-1层不会坏,或者在楼顶摔也不会坏)。 实验总是有风险的,摔坏的U盘不能再参加测试,可惜这种U盘太畅销了,你只能带有限的N个U盘去火星测试。 所以你需要知道在H和N确定的情况下,制定一套方案,宁可把这N个U盘砸坏,也要找到一个最小的次数K,使得无论U盘质量如何,总可以在K次实验后完成测试。 输入 输入文件有多组数据。 每组数据只有一行,即两个正整数N和H(1≤N≤15,1≤H≤1000)。 输入以00结束。 输出 对每组数据,只需输出一行,为最少的次数K。 样例输入 1 2 3 7 4 15 4 16 0 0 样例输出 2 3 4 5 提示 1.火星上的楼层数都是连续的,所以对H=2的情况,可能得到的测试结果是: a)在1层摔坏; b)在1层摔不坏而在2层摔坏; c)在2层摔不坏。 故对(N=1,H=2)情形,先在1层测,如果没摔坏,再在2层测,K=2。 2.你带去的N个U盘质量都是相同的,实验时的条件也是一致的。 3.在低层摔坏的在高层一定摔坏,在高层摔不坏的在低层一定摔不坏。 #include intvf[16][1001]; intmain() { inti,j,k,max,min,n,h; for(i=1;i<=1000;i++) vf[1][i]=i; for(i=1;i<=15;i++) { vf[i][1]=1; vf[i][2]=2; } for(i=2;i<=15;i++) for(j=3;j<=1000;j++) { min=1000000000; for(k=1;k<=(j+1)/2;k++) { max=vf[i-1][k]; if(vf[i][j-k-1]>max) max=vf[i][j-k-1]; max++; if(max min=max; } vf[i][j]=min; } scanf("%d%d",&n,&h); while(n) { printf("%d\n",vf[n][h]); scanf("%d%d",&n,&h); } return0; } Wujitu的RP守恒 时间限制: 1500ms 内存限制: 8192KB 总提交: 508(111users) 正确提交: 102(69users) 描述 话说天下的RP是守恒的,你的RP高了,我的RP可能就低了,你今天RP高了,明天RP可能就低了。 我们的RP总是在高高低低中不断变化。 有些事情做了是可以涨RP的,有的事情做了是要降RP的。 Wujitu在发现了这个道理后,决定在期末考试前多多积累人品。 他发现,他做的每件事情对RP有如下影响: (1)他做了的第一件事情是涨RP的 (2)如果他做的上一件事情是涨RP的,那么他做的下一件事情是降RP的 (3)如果他做的上一件事情是降RP的,那么他做的下一件事情是涨RP的 Wujitu现在积攒的人品是0。 涨RP记为RP值增加,降RP记为RP值减少。 Wujitu在期末考试前有N件事情可以做,每件事情都有自己的RP系数。 对于这些事情,Wujitu只可以有两种选择: 做,不做。 事情的先后顺序是一定的,也就是说Wujitu只可以按照给定好的顺序选择做不做该事情。 现在请你帮助Wujitu在期末考试之前,积攒到最多的RP。 输入 每组数据包括两行,第一行有一个整数N(N<=1000000),代表有N件事情;第二行有N个正整数,代表每件事情的RP值Ri[正数] Ri<=1000000 输出 输出结果仅包含一个整数,即Wujitu在期末前能积攒的最大RP值 样例输入 1 1 4 1 3 1 2 样例输出 1 4 #include intRP[1000001]; main() {longlongnumber; inti; longlongf[2],g[2]; while(scanf("%lld",&number)! =EOF) { if(number==0) printf("0\n"); if(number>0) { for(i=1;i<=number;i++) scanf("%d",&RP[i]); f[0]=0; g[0]=0; for(i=1;i<=number;i++) { if(f[(i-1)%2] f[i%2]=g[(i-1)%2]+RP[i]; else f[i%2]=f[(i-1)%2]; if(g[(i-1)%2] g[i%2]=f[(i-1)%2]-RP[i]; else g[i%2]=g[(i-1)%2]; } if(g[number%2]>f[number%2]) f[number%2]=g[number%2]; printf("%lld\n",f[number%2]); } } } 魔族密码 时间限制: 1000ms 内存限制: 8192KB 总提交: 250(115users) 正确提交: 134(106users) 描述 魔族现在使用一种新型的密码系统。 每一个密码都是一个给定的仅包含小写字母的英文单词表,每个单词至少包含1个字母,至多75个字母。 如果在一个由一个词或多个词组成的表中,除了最后一个以外,每个单词都被其后的一个单词所包含,即前一个单词是后一个单词的前缀,则称词表为一个词链。 例如下面单词组成了一个词链: i int integer 但下面的单词不组成词链: integer intern 现在你要做的就是在一个给定的单词表中取出一些词,组成最长的词链(包含单词数最多的词链)。 将它的单词数统计出来,就得到密码了。 这些文件的格式是,第一行是单词表中的单词数N(1<=N<=2000),下面每一行有一个单词,按字典顺序排列,中间也没有重复的单词! 要提交的文件中只要在第一行输出密码就行啦。 输入 第一行包含一个整数T,表示有T组数据。 对于每组数据,第一行包含一个整数N,表示有N个单词。 以下N行每行有1个字符串,为一个单词。 输出 最长的词链的长度。 样例输入 1 5 i int integer intern internet 样例输出 4 #include #include main() { intnumber,te; intn; inti,j; intlength; chara[2000][80]; intb[2001]; intmax; scanf("%d",&number); for(te=1;te<=number;te++) { scanf("%d",&n); for(i=0;i { scanf("%s",&a[i]); } for(i=0;i b[i]=1; for(i=1;i for(j=i-1;j>=0;j--) { length=strlen(a[j]); if(strncmp(a[i],a[j],length)==0) {b[i]+=b[j]; break; } else continue; } max=b[0]; for(i=0;i { if(max max=b[i]; } printf("%d\n",max); } } 装配线调度2 时间限制: 1000ms 内存限制: 1000KB 总提交: 477(129users) 正确提交: 86(65users) 描述 某汽车工厂有2个装配线,每个装配线有n个装配站(按顺序编号1~n),两个装配线对应的装配站执行相同的功能,但所用的时间可能不同。 经过第i条流水线(i=1,2)的第j个装配站所花的时间为Aij。 从第i条流水线的第j个装配站移到第j+1个装配站的时间可以忽略,而移到另外一个流水线的下一个装配站则需要一定的时间Tij。 汽车进入流水线不需要花时间,出流水线时需要花时间Tin。 汽车的装配需要按顺序经过所有装配站。 现在已知装配时间Aij和转移时间Tij,要求输出装配一辆汽车所需要的最短时间。 注意: 根据练习15.1-4压缩存储空间的指示精神,本题做了较为严格的内存限制(其实还可以更严)。 。 。 输入 第一行为一个整数T,表示有T组测试数据。 对于每组测试数据的第一行一个整数n(n<=100,000),表示有n个装配站。 接下来的n行按顺序给出了n个装配站信息,其中第j行有4个整数A1j,A2j,T1j,T2j。 输出 对于每组测试数据,输出两行: 第一行一个整数即最短时间。 第二行从n到1倒序输出经过的装配站所在的流水线的编号。 (数据保证最优方案只有一种) 样例输入 1 6 7 8 2 2 9 5 3 1 3 6 1 2 4 4 3 2 8 5 4 1 4 7 3 2 样例输出 35 1 2 2 1 2 2 奇怪的梦 时间限制: 1000ms 内存限制: 65536KB 总提交: 203(53users) 正确提交: 62(42users) 描述 上完算法课回来的路上,你仍然为DP的优美而赞叹不已。 正所谓日有所思,夜有所梦,午觉也不例外。 因为研究DP太过投入,睡午觉的时候你做了一个很奇怪的梦。 梦里你回到了19世纪。 那时的人们还没有计算机的概念。 而很不幸的,在时空旅行中你带上了你的笔记本。 所以很自然的,你成为了那个年代最伟大的科学家之一。 这天,你和一群科学家同伴聚会。 会上讨论了矩阵链乘法问题。 当时还没有很好的解决方法。 而你想到了刚刚算法课上讲到的动态规划方法(为什么是刚刚? ? 应该是很久以后......)。 PS: 有关矩阵链乘法问题参考算法导论第十五章第2节。 输入 第一行只有一个整数n,表示矩阵链的数目。 每条矩阵链描述如下: 第一行是一个整数m(0 表示一共有m个矩阵 接下来的m行每行一对整数Pi,Qi(0 表示矩阵Ai的维数。 输入数据保证矩阵相容。 输出 每条矩阵链输出两行。 第一行一个整数,表示最小的标量乘法次数。 第二行用加括号的方式描述此方法 当最优解不唯一时,按先左后右的顺序相乘。 例如有3个矩阵A1,A2,A3。 当((A1A2)A3)和(A1(A2A3))相等时,输出((A1A2)A3)。 样例输入 1 6 30 35 35 15 15 5 5 10 10 20 20 25 样例输出 15125 ((A1(A2A3))((A4A5)A6)) 又一个奇怪的梦 时间限制: 1000ms 内存限制: 65536KB 总提交: 140(64users) 正确提交: 62(50users) 描述 上完算法课回来的路上,你仍然为DP的优美而赞叹不已。 正所谓日有所思,夜有所梦,午觉也不例外。 因为研究DP太过投入,睡午觉的时候你做了一个很奇怪的梦。 梦里你回到了19世纪。 那时的人们还没有计算机的概念。 而很不幸的,在时空旅行中你带上了你的笔记本。 所以很自然的,你成为了那个年代最伟大的科学家之一。 这天,你和一群科学家同伴聚会。 会上讨论了矩阵链乘法问题。 不过这个时空的人们认为标量乘法次数越多越好。 这时你想到了刚刚算法课上讲到的动态规划方法(为什么是刚刚? ? 应该是很久以后......)。 PS: 有关矩阵链乘法问题参考算法导论第十五章第2节。 输入 第一行只有一个整数n,表示矩阵链的数目。 每条矩阵链描述如下: 第一行是一个整数m(0 表示一共有m个矩阵 接下来的m行每行一对整数Pi,Qi(0 表示矩阵Ai的维数。 输入数据保证矩阵相容。 输出 每条矩阵链输出两行。 第一行一个整数,表示最大的标量乘法次数。 第二行用加括号的方式描述此方法 当最优解不唯一时,按先右后左的顺序相乘。 例如有3个矩阵A1,A2,A3。 当((A1A2)A3)和(A1(A2A3))相等时,输出(A1(A2A3))。 样例输入 1 6 30 35 35 15 15 5 5 10 10 20 20 25 样例输出 58000 (A1((A2((A3A4)A5))A6)) 数字三角形 时间限制: 1000ms 内存限制: 65536KB 总提交: 226(131users) 正确提交: 122(115users) 描述 7 38 810 2774 55265 如上所示出的一个数字三角形宝塔。 数字三角形中的数字为不超过100的正整数。 现规定从最顶层走到最底层,每一步可沿左斜线向下或右斜线向下走。 假设三角形行数≤100,设计一个算法,找到从最顶层走到最底层的一条路径,使得沿着该路径所经过的数字的总和最大,输出最大值。 输入 第一行一个整数T,表示有T组测试数据。 对于每组测试数据: 第一行是三角形的行数N。 以后的N行分别是从最顶层到最底层的每一层中的数字。 输出 对于每组测试数据输出一行: 最佳路径所对应的最大值。 样例输入 1 5 7 3 8 8 1 0 2 7 7 4 5 5 2 6 5 样例输出 30 #include usingnamespacestd; inta[100][100]; intn; intmain() { intt; cin>>t; while(t--) { cin>>n; for(inti=0;i { for(intj=0;j<=i;j++) cin>>a[i][j]; } for(inti=n-1;i>0;i--) { for(intj=0;j { if(a[i][j]>a[i][j+1]) a[i-1][j]=a[i][j]+a[i-1][j]; else a[i-1][j]=a[i][j+1]+a[i-1][j]; } } cout< }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北航 DP 问题 整理