【线性DP】跳格子问题 + 光签题（取石子游戏）

$Part1跳格子$

LDUOJ 测试平台传送门

问题描述：

$Nikola$ 现在已经成为一个游戏里的重要人物。这个游戏是由一行 $N$ 个方格，$N$ 个方格用 $1$ 到 $N$ 的数字表示。
$Nikola$ 开始是在 $1$ 号位置，然后能够跳到其他的位置，$Nikola$ 的第一跳必须跳到 $2$ 号位置。随后的每一跳必须满足两个条件：

• 如果是向前跳，必须比前面一跳远一个方格。
• 如果是向后跳，必须和前面一跳一样远。

比如，在第一跳之后（当在 $2$ 号位置时），$Nikola$ 能够跳回 $1$ 号位置，或者向前跳到 $4$ 号位置。
每次他跳入一个位置，$Nikola$ 必须付费。$Nikola$ 的目标是从 $1$ 号位置尽可能便宜地跳到 $N$ 号位置。
写一个程序，看看 $Nikola$ 跳到 $N$ 号位置时最小的花费。

输入：

输入文件 $nikola.in$ 共有 $N+1$ 行。
第一行：包含一个整数$N$，$2\le N\le 1000$，它是位置的编号。
第$2..N+1$行：第$i+1$行表示第 $i$ 个方格的费用，是一个正整数，绝对不超过 $500$。

输出：

输出文件 $nikola.out$ 中只有一个数，表示 $Nikola$ 跳到 $N$ 号位置时最小的花费。

解题思路：
首先，我们需要确定的是所求答案所在的状态。对于所到达的每一个格子，要么从左边的某一个格子跳过来，要么从右边的某一个格子跳过来。按这种划分方式将所有方案划分成各个集合。我们可以用 $f[i][j]$ 来表示每一个集合。$f[i][j]$ 表示从第 $j$ 个格子跳到第 $i$ 个格子的最小花费。
状态转移：

1、
if (j - i >= 1) f[j][i] = min(f[j][i], f[j - i][i - 1] + a[j]);
2、
if(i + j <= n) f[j][i] = min(f[j][i], f[j + i][i] + a[j]);
1
2
3
4

从状态转移方程式中可以看出，转移的方式是由已知的当前状态去更新后面未确定的多种状态。

上代码：

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
int n;
int a[1010];
int f[1010][1010];//f[i][j]指从第j个格子跳到第i个格子的最小花费
int main()
{
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i];
	memset(f, 0x3f, sizeof f);
	f[2][1] = a[2];
	for (int i = 1;i <= n;i++)
	{
		//由i更新j  左 -> 右
		for (int j = 1;j <= n;j++)
		{
			if (j - i >= 1) f[j][i] = min(f[j][i], f[j - i][i - 1] + a[j]);
		}
		//由i更新j 右 -> 左
		for (int j = n;j >= 1;j--)
		{
			if(i + j <= n) f[j][i] = min(f[j][i], f[j + i][i] + a[j]);
		}
	}
	int ans = 0x3f3f3f3f;
	for (int i = 1;i <= n;i++)
	{
		//cout << f[n][i] << " ";
		ans = min(ans, f[n][i]);
	}
	cout << ans << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

$Part2光签题Ⅱ$

LDUOJ 测试平台传送门
题目描述：

背景：光光被说题目出的太简单了，特此来谢罪了
题目来源：光光的签到题 $=$ 光签题
光光说：”我不喜欢博弈论，但是我要把博弈论变成$【dp】$“
给出 $N$ 堆石子，你有 $M$ 次机会，每次只能拿 $1$ 堆石子中的 $x$ 个，当然需要花费：$x^2$。
求出拿完所有石子的最小花费
如果你求出最小花费，那么光光算你赢，否则应该算光光赢了吧（九折水平？）

输入：

两个整数 $N,M$
接下来 $N$ 个整数 $a_i$ 代表每堆石子的数量。

输出：

一个整数代表最小花费。

数据范围：

$1\le N\le 2000$
$N\le M\le 4000$
$1\le a_i\le 100$

解题思路：
根据数据范围，我们可以先计算一下时间复杂度，$N$ 堆石头，$M$ 次机会，每堆石头最多能拿 $a_i$ 次。2000×4000×100，大约是8e8的复杂度，在计算的过程中，还可以用一些优化条件，这样可以使复杂度降低一点，可以在$1s$之内跑完。
状态表示：$f[i][j]$ 表示拿完前 $i$ 堆石头一共使用了 $j$ 次机会所花费的最小代价。
属性：求最小值
状态转移：

f[i][j] = min(f[i][j], f[i - 1][j - k] + w);
这里再解释一下这个w,用k次机会拿完第i堆石头所花费的代价；
很明显，对于第i堆石头而言，在所用机会k确定的情况下，
让每次拿走的石头个数之间的差值最小可以使得所花费的代价最小。
1
2
3
4

上 $AC$ 代码：

$Time:314MS$
$Memory:31.88MB$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[2010][4010];//f[i][j]表示拿完前i堆,并且一共花费j次机会
int a[2010];
int main()
{
	//freopen("6.in","r",stdin); 
	int n, m;scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i++) scanf("%d", &a[i]);
	memset(f, 0x3f, sizeof f);
	for (int i = 0;i <= m;i++) f[0][i] = 0;
	for (int i = 1;i <= n;i++)
	{
		for (int k = 1;k <= min(a[i], m);k++)
		{
			int c = a[i] / k;
			int d = a[i] % k;
			int w = d * (c + 1) * (c + 1) + (k - d) * c * c;
			//下面这层循环的目的是拿当前所处状态
			//去更新后面所能更新到的未知状态
			//至于j的始端值与末端值的选择；
			//是根据每一堆石头都至少花费一次机会来确定的
			for (int j = k + i - 1;j <= m - n + i;j++) f[i][j] = min(f[i][j], f[i - 1][j - k] + w);
		}
	}
	printf("%d", f[n][m]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

小小的疑惑：
个人感觉下面这段代码的时间复杂度和上面AC代码的时间复杂度是一致的，带入超时数据进行循环次数测定，发现二则相差的次数也不算太多，下图展示出二者的循环次数：

有点疑惑的就是二则只是相差3e6而已嘛，竟然给T掉，这就很烦。
二者的思路大致是一样的只是在处理第二层循环与第三层循环的额时候给交换了一下考虑的次序。知道原因的大佬们请留步，给老弟一些指点吧，感谢，感谢！