网站开发四个重点东莞网站建设 织梦

网站开发四个重点,东莞网站建设 织梦,网线制作实验原理,密云免费网站建设题目背景NOIP2010 提高组 T2题目描述小明过生日的时候#xff0c;爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行 N 个格子#xff0c;每个格子上一个分数#xff08;非负整数#xff09;。棋盘第 1 格是唯一的起点#xff0c;第 N 格是终点#xff0c;游戏要求玩家控…题目背景NOIP2010 提高组 T2题目描述小明过生日的时候爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行 N 个格子每个格子上一个分数非负整数。棋盘第 1 格是唯一的起点第 N 格是终点游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中 M 张爬行卡片分成 4 种不同的类型M 张卡片中不一定包含所有 4 种类型的卡片见样例每种类型的卡片上分别标有 1,2,3,4 四个数字之一表示使用这种卡片后乌龟棋子将向前爬行相应的格子数。游戏中玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片控制乌龟棋子前进相应的格子数每张卡片只能使用一次。游戏中乌龟棋子自动获得起点格子的分数并且在后续的爬行中每到达一个格子就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。很明显用不同的爬行卡片使用顺序会使得最终游戏的得分不同小明想要找到一种卡片使用顺序使得最终游戏得分最多。现在告诉你棋盘上每个格子的分数和所有的爬行卡片你能告诉小明他最多能得到多少分吗输入格式每行中两个数之间用一个空格隔开。第 1 行 2 个正整数 N,M分别表示棋盘格子数和爬行卡片数。第 2 行 N 个非负整数a1​,a2​,…,aN​其中 ai​ 表示棋盘第 i 个格子上的分数。第 3 行 M 个整数b1​,b2​,…,bM​表示 M 张爬行卡片上的数字。输入数据保证到达终点时刚好用光 M 张爬行卡片。输出格式一个整数表示小明最多能得到的分数。输入输出样例输入 #1复制9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1输出 #1复制73说明/提示每个测试点 1s。小明使用爬行卡片顺序为 1,1,3,1,2得到的分数为 610148181773。注意由于起点是 1所以自动获得第 1 格的分数 6。对于 30% 的数据有 1≤N≤30,1≤M≤12。对于 50% 的数据有 1≤N≤120,1≤M≤50且 4 种爬行卡片每种卡片的张数不会超过 20。对于 100% 的数据有 1≤N≤350,1≤M≤120且 4 种爬行卡片每种卡片的张数不会超过 400≤ai​≤100(1≤i≤N),1≤bi​≤4(1≤i≤M)。#includebits/stdc.h using namespace std; const int N360,M50; int f[M][M][M][M],cnt[5]; int x[N]; int n,m; int main() { cinnm; for(int i1;in;i) { cinx[i]; } for(int i1;im;i) { int t; cint; cnt[t]; } f[0][0][0][0]x[1]; for(int a0;acnt[1];a) { for(int b0;bcnt[2];b) { for(int c0;ccnt[3];c) { for(int d0;dcnt[4];d) { int i1ab*2c*3d*4; int tf[a][b][c][d]; if(a) tmax(t,f[a-1][b][c][d]x[i]); if(b) tmax(t,f[a][b-1][c][d]x[i]); if(c) tmax(t,f[a][b][c-1][d]x[i]); if(d) tmax(t,f[a][b][c][d-1]x[i]); } } } } coutf[cnt[1]][cnt[2]][cnt[3]][cnt[4]]endl; return 0; }