网站开发如何建设公共页面,视频网站内容规划,设计网站大全国内,杭州网站建设哪家强3628: [JLOI2014]天天酷跑 Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 121 Solved: 44[Submit][Status][Discuss]Description 在游戏天天酷跑中#xff0c;最爽的应该是超级奖励模式了吧#xff0c;没有一切障碍#xff0c;可以尽情的吃金币#xff0c;现在请你控制… 3628: [JLOI2014]天天酷跑 Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 121 Solved: 44[Submit][Status][Discuss] Description 在游戏天天酷跑中最爽的应该是超级奖励模式了吧没有一切障碍可以尽情的吃金币现在请你控制游戏角色来获得尽可能多的分数。 游戏界面离散为一个长度为1~n高度为1~m初始点为01的矩阵图。每个格子上都有收益-1~1000-1表示该点不能通过。游戏角色从起点一路奔跑向终点中途可以跳跃来获得更高的分数在空中还能进行连跳。游戏开始前你可以设定跳跃的高度以及能连跳的次数初始跳跃高度为1连跳数为1最多为5升级跳跃高度和连跳都需要一定的花费。跳跃高度设定完后游戏角色每次跳跃高度都将固定连跳必须在下落过程中可以使用。所有操作都将在整点上完成需要保证设定完的跳跃高度及连跳数无法跳出游戏高度上限。 以下是连跳数为2连跳跳跃高度为2的跳跃方案 Input 第一行四个整数nmcost1cost2。nm如题意所示cost1cost2分别表示每升一级跳跃高度连跳数所需的花费。 接下来m行每行n个数。第i行第j个数表示地图中高度为i长度在第j列处的收益。 Output 如果无法跑出终点线就输出“mission failed”否则输出一行三个数分别表示最大收益及最大收益时最小的连跳数最大收益最小连跳数时最小的跳跃高度。 Sample Input 7 4 6 10 9 4 7 7 4 3 2 18 8 9 4 15 12 4 19 2 4 7 10 18 12 8 1 13 14 16 0 14 Sample Output 67 1 2 HINT 提示 20%数据满足 m2 n100000; 另有80%数据 n100002m20其中20%数据 2n10m10; /*定义状态f[i][j][o]表示处于xy这个位置还剩余o次连跳数的最大收益如果是跑——f[i][j][o]max(f[i][j1][o]w[i][j]) w[i][j]为这点的权值如果是跳的话——f[i][j][o]max(f[i跳跃高度high][jhigh][o--]hhhw[i][j]) hhh跳跃上升过程中得到的金币数。
*/
#includecstdio
#includecstdlib
#includecstring
#includeiostream
using namespace std;
#define inf 130
#define maxn 100010
bool vis[25][maxn][6];
int f[25][maxn][6],map[25][maxn];
int n,m,c1,c2,ans-inf,ans1,ans2,h,num;
int dfs(int x,int y,int now){if(xn)return 0;if(map[y][x]-1)return -inf;if(vis[y][x][now])return f[y][x][now];int tot-inf,sum0;bool flag1;if(y1)now0;if(nownum){for(int i1;ih;i){if(map[yi][xi]-1){flag0;break;}summap[yi][xi];}if(flag)totmax(tot,sumdfs(xh,yh,now1));}if(y1)totmax(tot,dfs(x1,y,0));if(y1)totmax(tot,dfs(x1,y-1,now));vis[y][x][now]1;f[y][x][now]totmap[y][x];return f[y][x][now];
}
int main(){scanf(%d%d%d%d,n,m,c1,c2);for(int i1;im;i)for(int j1;jn;j)scanf(%d,map[i][j]);for(num1;num5;num){for(h1;h*numm;h){memset(f,-1,sizeof(f));memset(vis,0,sizeof(vis));int totdfs(0,1,m)-c2*(num-1)-c1*(h-1);if(anstot)anstot,ans1num,ans2h;}}if(ans0)printf(%d %d %d,ans,ans1,ans2);else printf(mission failed);return 0;
} 转载于:https://www.cnblogs.com/thmyl/p/7485186.html
