|
NOIP历年考试中动态规划都是一个非常重要的考点。今天为大家带来常考的动态规划题型及知识点介绍。欢迎大家补充讨论。 除了以上描述以外，在NOIP中经常出现的动态规划类问题还有 坐标规则型动态规划动态规划算法之资源分配问题树型动态规划 这三个点我们将在后面的文章中提及。 如果同学们有更多关于动态规划类习题的解题经验及知识点补充，欢迎在文章底部留言给我们。 坐标规则型动态规划 例题 Robots 题目描述 在一个n∗mn∗m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。 问：最多能拾多少垃圾。在最多的情况下，有多少种拾垃圾方案？ 数据范围:n≤100,m≤100n≤100,m≤100 样例分析 最多能拾5块。有4种方法。 解析 ： 代码： #include <cstdio> #include <cstring> #include <algorithm> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) typedef long long LL; const int size = 100+10; int f[size][size]; bool mp[size][size]; int n,m; int main() { scanf('%d%d',&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf('%d',&mp[i][j]); } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=Max(f[i-1][j],f[i][j-1])+mp[i][j]; printf('%d\n',f[n][m]); return 0; } 矩阵取数游戏 （NOIP2007） 具体描述见链接：矩阵取数游戏 解析 ： 代码 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=80+10; struct BIGNUM { int num[maxn],len; BIGNUM(){memset(num,0,sizeof(num));len=1;} BIGNUM operator = (const char str[]) { len=strlen(str); for(int i=0;i<len;i++) num[i]=str[len-i-1]-'0'; while(num[len-1]==0&&len>1) len--; return *this; } BIGNUM operator = (const int n) { int tmp=n; len=1; do { num[len-1]=tmp%10; tmp/=10;len++; }while(tmp>0); while(num[len-1]==0&&len>1) len--; return *this; } BIGNUM operator + (const BIGNUM &rhs) const { BIGNUM tmp; tmp.len=max(len,rhs.len)+1; for(int i=0;i<tmp.len;i++) { tmp.num[i]+=num[i]+rhs.num[i]; tmp.num[i+1]=tmp.num[i]/10; tmp.num[i]%=10; } while(tmp.num[tmp.len-1]==0&&tmp.len>1) tmp.len--; return tmp; } BIGNUM operator * (const BIGNUM &rhs) const { BIGNUM tmp; tmp.len=len+rhs.len; for(int i=0;i<len;i++) for(int j=0;j<rhs.len;j++) { tmp.num[i+j]+=num[i]*rhs.num[j]; tmp.num[i+j+1]+=tmp.num[i+j]/10; tmp.num[i+j]%=10; } while(tmp.num[tmp.len-1]==0&&tmp.len>1) tmp.len--; return tmp; } bool operator < (const BIGNUM &rhs) const { if(len>rhs.len) return false; if(len<rhs.len) return true; for(int i=len-1;i>=0;i--) if(num[i]!=rhs.num[i]) return num[i]<rhs.num[i]; return false; } void print() { for(int i=len-1;i>=0;i--) printf('%d',num[i]); } }dp[maxn][maxn]; BIGNUM ans; int a[maxn]; int main() { int n,m; scanf('%d%d',&n,&m); BIGNUM pow; pow=2; for(int i=1;i<=n;i++) { memset(dp,0,sizeof(dp)); for(int j=1;j<=m;j++) { scanf('%d',&a[j]); dp[j][j]=a[j]*2; } for(int x=2;x<=m;x++) for(int l=1;l<=m;l++) { int r=l+x-1; if(r>m) continue; dp[l][r]=max(dp[l+1][r]*pow+dp[l][l],dp[l][r-1]*pow+dp[r][r]);//dp } ans=ans+dp[1][m]; } ans.print(); return 0; } 传纸条(NOIP2008) 具体描述见链接：传纸条 解析： 刚开始可能想用一个贪心思想： 求出1个纸条从（1，1）到（M,N）的路线最大值. 删除路径上的点值 再求出1个纸条从（M,N） 到（1，1）的路线最大值. 统计两次和 然后就很容易发现有反例，哈哈。 然后你想怎么搞呢，既然方向有限定，那么符合dp特性，就可以dp了。 由于小渊和小轩的路径可逆，因此，尽管出发点不同，但都可以看成同时从(1,1)出发到达(M,N)点。 (原谅我用mathtype写的，懒得搞成mathjax了） 其中 代码： #include <bits/stdc++.h> using namespace std; const int size=55; int a[size][size]; int f[size][size][size][size]; int n,m; int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=1;k<=n;k++) { for(int l=1;l<=m;l++) { f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]); f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k-1][l]); f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l-1]); f[i][j][k][l]+=(a[i][j]+a[k][l]); if(i==k&&j==l) { f[i][j][k][l]-=a[i][j]; } } } } } cout<<f[n][m][n][m]<<endl; return 0; } 免费馅饼 题目描述 : SERKOI最新推出了一种叫做“免费馅饼”的游戏。 游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时游戏者站在舞台的正中央，手里拿着一个托盘。下图为天幕的高度为4格时某一个时刻游戏者接馅饼的情景。 游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。 馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时，在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。 当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。 输入 输入文件的第一行是用空格隔开的两个正整数，分别给出了舞台的宽度W（1到99之间的奇数）和高度H（1到100之间的整数）。 接下来依馅饼的初始下落时间顺序给出了所有馅饼的信息。每一行给出了一块馅饼的信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0到1000秒），水平位置、下落速度（1到100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。 输入文件中同一行相邻两项之间用一个或多个空格隔开。 输出 输出文件的第一行给出了一个正整数，表示你的程序所收集的最大分数之和。 解析 刚开始看到这道题却没什么思路，两个物品都同时在动，似乎很复杂的样子。 看了ppt后面的题解后，可以算出每个时刻落到最底层的每个格子有多少分值的馅饼。 如果将馅饼当成参照物，则馅饼向下落，可以看成馅饼不动，人往上走去摘取馅饼，这样人每1时刻都可以走到上一行的5个格子，如图： 计算出每个格子每个时刻可能达到的馅饼分值，填入W*H的天幕表。 其中C[i,j]表示天幕的第i行第j列的馅饼分值，即第i时刻，馅饼落到最底行的馅饼分值。
代码: #include <cstdio> #include <cstring> #include <algorithm> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) const int size = 1000+10; int st; int f[size][110]; int c[size*10],x[size*10],t[size*10],v[size*10]; int n=1,h,w; int m=0,time=0; int mx(int i,int j) { int m=0; if(f[i+1][j-2]>m and j-2>0) {m=f[i+1][j-2];st=-2;} if(f[i+1][j-1]>m and j-1>0) {m=f[i+1][j-1];st=-1;} if(f[i+1][j]>m) {m=f[i+1][j];st=0;} if(f[i+1][j+1]>m) {m=f[i+1][j+1];st=1;} if(f[i+1][j+2]>m) {m=f[i+1][j+2];st=2;} return m; } int main() { freopen('freecake.in','r',stdin); scanf('%d%d',&w,&h); h--; while(~scanf('%d%d%d%d',&t[n],&x[n],&v[n],&c[n])) { if(h%v[n]==0) { t[n]+=h/v[n];time=Max(time,t[n]); n++; } } memset(f,0,sizeof f); for(int i=1;i<=n;i++) f[t[i]][x[i]]+=c[i]; for(int i=time-1;i>=0;i--) for(int j=w;j>0;j--) f[i][j]+=mx(i,j); printf('%d\n',f[0][w/2+1]); for(int i=0,j=w/2+1;;i++) { if(mx(i,j)==0) break; j+=st;printf('%d\n',st); } return 0; } 三角蛋糕 题目描述 一块边长为n的正三角形的大蛋糕，一些被老鼠咬坏了，如下图黑色部分。 现想把该蛋糕切出一块最大的没被老鼠咬坏正三角形的蛋糕； 求切出的最大的三角形面积 范围：n≤100。 解析
代码 #include <cstdio> #include <cstring> #include <algorithm> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) typedef long long LL; const int size = 200+10; int a[size][size],n; char st[size]; int main() { scanf('%d',&n); for(int i=1;i<=n;i++) { scanf('%s',st+i); for(int j=1;j<=2*n-i;j++) { if(st[j]=='-') a[i][j]=a[i][j-1]+1; else a[i][j]=0; } } int ans=0,k; for(int i=1;i<=n;i++) for(int j=i;j<=2*n-i;j++) { if(a[i][j]) { if(!(i*j&1) and (i&1||j&1)) for(k=1;a[i+k][j+k]>=k*2+1;k++); else for(k=1;a[i-k][j+k]>=k*2+1;k++); ans=Max(ans,k*k); } } printf('%d\n',ans); return 0; } 总结 坐标规则类动态规划有一个共性，那就是在一个矩阵中（一般是二维矩阵，当然可能有更加复杂的图形）给出一些规则，然后按规则去做某些决策。 思考这类问题的基本方法是：以坐标为状态，坐标之间的转换关系，一般利用问题给出的规则进行决策转移。
|
|
|
