P1541 [NOIP2010 提高组] 乌龟棋

[NOIP2010 提高组] 乌龟棋

题目背景

NOIP2010 提高组 T2

题目描述

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（$M$ 张卡片中不一定包含所有 $4$ 种类型的卡片，见样例），每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

每行中两个数之间用一个空格隔开。

第 $1$ 行 $2$ 个正整数 $N,M$，分别表示棋盘格子数和爬行卡片数。

第 $2$ 行 $N$ 个非负整数，$a_1,a_2,…,a_N$，其中 $a_i$ 表示棋盘第 $i$ 个格子上的分数。

第 $3$ 行 $M$ 个整数，$b_1,b_2,…,b_M$，表示 $M$ 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 $M$ 张爬行卡片。

输出格式

一个整数，表示小明最多能得到的分数。

样例 #1

样例输入 #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$，得到的分数为 $6+10+14+8+18+17=73$。注意，由于起点是 $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$ 种爬行卡片，每种卡片的张数不会超过 $40$；$0≤a_i≤100,1≤i≤N,1≤b_i≤4,1≤i≤M$。

`//本题要求最多得多少分。集合可看作每种卡片拿。。。张，对应的分数和的集合的最大值。状态划分为四种：
//f(i-1,j,k,z),f(i,j-1,k,z),f(i,j,k-1,z),f(i,j,k,z-1)最后加上最后一步的分数然后取max.
//用一个计数器统计每种卡牌出现次数。

include

include

const int N = 100,M=360;
int f[N][N][N][N];
int n, m;
int a[M], b[M];
int v[M];
using namespace std;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];// 分数
}
for (int i = 1; i <= m; i++)
{
cin >> b[i];
v[b[i]]++;
}
f[0][0][0][0] = a[1];//开始在第一格。
for (int i = 0; i <= v[1]; i++)//枚举每种步数多少张。
{
for (int j = 0; j <= v[2]; j++)
{
for (int k = 0; k <= v[3]; k++)
{
for (int z = 0; z <= v[4]; z++)
{
int u = 1 + i * 1 + j * 2 + k * 3 + z * 4;//计算步数
if (i!=0) f[i][j][k][z] = max(f[i][j][k][z], f[i - 1][j][k][z] + a[u]);//如果没有步数为一的
if (j!=0)f[i][j][k][z] = max(f[i][j][k][z], f[i][j - 1][k][z] + a[u]);
if (k!=0)f[i][j][k][z] = max(f[i][j][k][z], f[i][j][k-1][z] + a[u]);
if (z!=0)f[i][j][k][z] = max(f[i][j][k][z], f[i][j][k][z-1] + a[u]);
}
}
}
}
cout << f[v[1]][v[2]][v[3]][v[4]] << endl;

}`

P4933 大师

大师

题目背景

建筑大师最近在跟着数学大师 ljt12138 学数学，今天他学了等差数列，ljt12138 决定给他留一道练习题。

题目描述

ljt12138 首先建了 $n$ 个特斯拉电磁塔，这些电塔排成一排，从左到右依次标号为 $1$ 到 $n$，第 $i$ 个电塔的高度为 $h[i]$。

建筑大师需要从中选出一些电塔，然后这些电塔就会缩到地下去。这时候，如果留在地上的电塔的高度，从左向右构成了一个等差数列，那么这个选择方案就会被认为是美观的。

建筑大师需要求出，一共有多少种美观的选择方案，答案模 $998244353$。

注意，如果地上只留了一个或者两个电塔，那么这种方案也是美观的。地上没有电塔的方案被认为是不美观的。

同时也要注意，等差数列的公差也可以为负数。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个非负整数，第 $i$ 个整数是第 $i$ 个电塔的高度 $h[i]$。

输出格式

输出一个整数，表示美观的方案数模 $998244353$ 的值。

样例 #1

样例输入 #1

8
13 14 6 20 27 34 34 41

样例输出 #1

50

样例 #2

样例输入 #2

100
90 1004 171 99 1835 108 81 117 141 126 135 144 81 153 193 81 962 162 1493 171 1780 864 297 180 532 1781 189 1059 198 333 1593 824 207 1877 216 270 225 1131 336 1875 362 234 81 288 1550 243 463 1755 252 406 261 270 279 288 1393 261 1263 297 135 333 872 234 881 180 198 81 225 306 180 90 315 81 81 198 252 81 297 1336 1140 1238 81 198 297 661 81 1372 469 1132 81 126 324 333 342 81 351 481 279 1770 1225 549

样例输出 #2

11153

提示

设 $v$ 为最高的电塔高度。

对于前 $30%$ 的数据，$n \le 20 $。

对于前 $60%$ 的数据，$n \le 100$，$v \le 2 \times 10^3$。

对于另外 $20%$ 的数据，所有电塔的高度构成一个等差数列。

对于 $100%$ 的数据，$n \le 10^3$，$v \leq2 \times 10^4$。

集合：从前i个塔中选，其等差为h[i]-h[j]的所有情况。
状态可划分为f(j,h[i]-h[j])+1;//考虑最后一个状态的前一个状态。
最后模上998244353即可

`#include

include

include

const int N = 1010, M = 50010;
int h[N];
int f[N][M];
int n;
int res;

using namespace std;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> h[i];
}
for (int i = 1; i <= n; i++)
{
res++;
for (int j = 1; j < i; j++)
{

		f[i][h[i] - h[j]+20010] += f[j][h[i] - h[j]+20010] + 1;
		f[i][h[i] - h[j]+20010] %= 998244353;
		res = (res+f[j][h[i] - h[j]+20010]+1)%998244353;
	}
}
cout << res;








return 0;

}`