这题我有一点点锅，题面写得没有特别清楚，容易被误解为只有直接依赖会得不到分，实际上间接的依赖也会丢分。
比如子任务 2 依赖子任务 1，子任务 3 依赖子任务 2。那么子任务 1 如果错了，子任务 3 也拿不到分。
#include <bits/stdc++.h>
using namespace std;
int a[5][5];
int score[5];
int main()
{
freopen("chen.in", "r", stdin);
freopen("chen.out", "w", stdout);
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
cin >> a[i][j];
for (int no = 1; no <= 4; no++)
{
for (int i = 1; i <= 4; i++)
score[i] = i * 10;
score[no] = 0;
if (score[1] == 0 && a[1][2] == 1)
score[2] = 0;
if (score[1] == 0 && a[1][3] == 1)
score[3] = 0;
if (score[1] == 0 && a[1][4] == 1)
score[4] = 0;
if (score[2] == 0 && a[2][3] == 1)
score[3] = 0;
if (score[2] == 0 && a[2][4] == 1)
score[4] = 0;
if (score[3] == 0 && a[3][4] == 1)
score[4] = 0;
cout << score[1] + score[2] + score[3] + score[4] << " ";
}
return 0;
}
诈骗题。实际上答案就是长度大于等于 的最大子段和。
首先容易发现 Kitten 到过的城市必然是某段子段，并且不可能只待在一个城市，因为 33DAI 后面来了会让他输掉游戏。
所以如果能达成“长度大于等于 的最大子段和”必然就是最优解，而这必然能达成。对于区间 ，它只需要在某个端点声东击西，然后往另一个端点走就可以了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1000000;
int n;
int a[MAXN + 5];
int sum[MAXN + 5];
signed main()
{
freopen("sheng.in", "r", stdin);
freopen("sheng.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + a[i];
int ans = sum[2];
int minSum = 0;
for (int i = 3; i <= n; i++)
{
minSum = min(minSum, sum[i - 2]);
ans = max(ans, sum[i] - minSum);
}
cout << ans;
return 0;
}
灵感来源：https://www.luogu.com.cn/problem/CF902B
实际上这道题我们可以把每个数字 和他去掉了最高位之后的剩余部分 ，建立一个 到 的父子关系，从而构建一棵树。比如假设有 ，就可以构建下面这棵树。
2 -> 12 -> 312
\ \-> 412
\->32
这样这题就转换成了灵感来源那道题了，给一个点染色就会给整个子树染色。容易发现不可能先染色子节点再染色它的某个祖先节点。所以可以从根节点开始，如果和目标不一样就变颜色，并给子节点改成对应的颜色。
当然进一步总结会发现，也就是每个节点如果和父节点颜色不一样，操作次数就要加 。
另外这题还给了一些部分分，子任务 1,3 只需要输出 即可。因为 是 的时候只要给 染色就好了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
int n;
int a[N + 5]; // 目标颜色
int b[N + 5]; // 当前颜色
vector<int> e[N + 5];
// 去掉最高位
int fa(int x)
{
for (int i = 1000000; i >= 10; i /= 10)
if (x >= i)
return x % i;
return x;
}
int main()
{
freopen("wu.in", "r", stdin);
freopen("wu.out", "w", stdout);
cin >> n;
for (int i = 0; i <= n; i++)
{
cin >> a[i];
e[fa(i)].push_back(i);
}
int ans = 0;
for (int u = 0; u <= n; u++)
{
if (b[u] == 0 || b[u] != a[u])
{
ans++;
b[u] = a[u];
}
for (int v : e[u])
b[v] = a[u];
}
cout << ans;
return 0;
}
首先子任务 1 送了 10 分，特判所有结果就好。
实际上这题的 dp 属性很容易被发现。两个人都是用最有走法，所以当你求 ，左边先走的最大得分，第一步只有两种情况：
而当你求 ，右边先走的最小得分，第一步也是两种情况：
由此直接记忆化搜索就好了，当然熟悉的同学也会发现这就是个简单的区间 dp 问题，并且还是个转移只要 的区间 dp。状态定义和转移方程看下面的代码吧。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 5000;
int n;
int a[MAXN + 5];
int f[MAXN + 5][MAXN + 5]; // l~r 33DAI 先手的得分
int g[MAXN + 5][MAXN + 5]; // l~r kitten 先手的得分
signed main()
{
freopen("an.in", "r", stdin);
freopen("an.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int len = 2; len <= n; len++)
{
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
// 不能走
if (len == 2)
{
f[l][r] = g[l][r] = a[l] - a[r];
continue;
}
// 走一步
f[l][r] = g[l + 1][r] + a[l];
g[l][r] = f[l][r - 1] - a[r];
// 可以走两步
if (len > 3)
{
f[l][r] = max(f[l][r], g[l + 2][r] + a[l]);
g[l][r] = min(g[l][r], f[l][r - 2] - a[r]);
}
}
}
cout << f[1][n];
return 0;
}