真题实战(坐标规则型动态规划)-NOIP提高组历年高频考点(5)

在NOIP中经常出现的动态规划类问题还有

坐标规则型动态规划

动态规划算法之资源分配问题

树型动态规划

这三个点我们将在后面的文章中提及。

动态规划之状态转移方程-NOIP提高组历年高频考点(4)

动态规划之状态压缩DP-NOIP提高组历年高频考点(3)

动态规划背包模型-NOIP提高组历年高频考点(2)

动态规划-NOIP提高组历年高频考点(1)

坐标规则型动态规划

例题

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;

}

总结

坐标规则类动态规划有一个共性,那就是在一个矩阵中(一般是二维矩阵,当然可能有更加复杂的图形)给出一些规则,然后按规则去做某些决策。

思考这类问题的基本方法是:以坐标为状态,坐标之间的转换关系,一般利用问题给出的规则进行决策转移。

---------------------

(0)

相关推荐