原创 | codeforces 1443D，解法简单，思维缜密的动态规划问题
原创 | codeforces 1443D，解法简单，思维缜密的动态规划问题
大家好，欢迎来到周末算法题。
今天选择的问题是上周的比赛的D题，这题是全场倒数第三题，截止到现在一共通过了2800余人。这题的思路不算难，但是思考过程非常有趣，这也是这一期选择它的原因。
链接：https://codeforces.com/contest/1443
废话就先说到这里，下面我们就来看题吧。
题意
给定n个整数，对于这n个整数我们可以采取两种操作。第一种操作是在数组左侧选择连续的k个整数减1，第二种操作是选择右侧的连续k个整数减1。
比如假设数组是[3, 2, 2, 1, 4]，比如我们选择k=2，取最左侧进行操作，那么我们会得到[2, 1, 2, 1, 4]。如果我们选择k=3，再取右侧进行操作，可以得到[2, 1, 1, 0, 3]。
现在我们想要知道，给定这样的数组，我们能否通过这两个操作将数组清空。如果可以输出YES，否则的话输出NO。
样例
题解
由于我们对于k没有限制，最多我们可以一次对数组内的n个元素全部减一。所以k不是限制我们的因素，最大的限制其实是在元素本身。
我们分析一下会发现，由于数组当中的元素大小不一，这其实是隐形的限制。举个例子，比如[2, 8, 3]。由于我们只能从两侧开始选择元素进行操作，所以由于2和3比较小，会导致我们没有办法把中间的8消除完。当然无法消除的原因可能有好几种，但基本上都是由于元素的大小不一导致的。
首先我们对这个问题进行一个简单的建模，题目当中没有限制执行的次数，所以减一次和减很多次是一样的。我们可以把可以合并的操作合并在一起，理解成执行一次可以减去任意的值。并且我们可以把操作反向理解，把数组当中的值看成是容器，这样我们从数组当中减去值的操作，就可以等价理解成向容器当中输入水流，这样会容易理解一些。
我的第一想法很简单，我们可以求出每个位置能够从左侧和右侧分别获得的最大数值。只要左右两侧能够获取的流量之和大于等于容器的容积，那么就说明我们可以获取到足够的流量灌满所有的容器。
我很快就写出了代码，建了一个二维数组，dp[i][0]表示第i个元素从左侧源头能够获取的最大流量。dp[i][1]表示第i个元素可以从右侧源头获取到的最大流量。由于我们需要保证每个容器存储的体积不能超过容量，所以我们需要很容易得出递推关系。
dp[i][0] = min(dp[i-1][0], a[i])
关系明确了很容易写出代码：
using namespace std;
int a[30006], dp[30006][2];
int main() {
int t, n;
scanf("%d", &t);
rep(z, 0, t) {
scanf("%d", &n);
rep(i, 1, n+1) scanf("%d", &a[i]);
MEM(dp, 0x3f);
// 从左侧递推，获取dp[i][0]
rep(i, 1, n+1) {
dp[i][0] = min(dp[i-1][0], a[i]);
}
// 从右侧递推，获取dp[i][1]
Rep(i, n, 0) {
dp[i][1] = min(dp[i+1][1], a[i]);
}
bool flag = 1;
rep(i, 1, n+1) {
// 如果存在某个元素从左右两侧获取的流量之和无法灌满
// 则返回NO
if (dp[i][0] + dp[i][1] < a[i]) {
flag = 0;
break;
}
}
puts(flag ? "YES" : "NO");
}
return 0;
}
但是很遗憾，这样不能AC，因为dp的数组维护的其实是某个位置从左侧和从右侧能够获取的最大值，这是一个理想情况，很有可能这个理想情况是无法实现的。
举个很简单的反例：[2, 4, 2, 4, 2]，这些元素左右两边能够获取到的最大流量值都是2，但是这里是有问题的。观察一下会发现数组当中的两个4是无法同时满足的，无法满足的原因是因为中间的2限制了通过的流量。虽然理论上从左往右和从右往左能够通过的流量上限都是2，但是这个上限是无法同时取到的。
这个问题用上述的方法是解决不了的，所以需要重新构思。这里我们深入分析会发现一个比较麻烦的点，在于每个点都有两个源头，我们无法确定流量分配。不过这个问题也很好解决，因为左右两边的流量是没有区别的。所以我们可以以某一侧为主，剩余不够的流量再由另一侧补充。
比如我们可以以左侧为主，把左侧能够获取的流量开启到最大，不够地再通过右侧补充。如果右侧的流量无法补充，那么就说明无解。
我们用dp[i][0]记录i位置从左侧获取的流量，dp[i][1]记录i位置从右侧获取的流量。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
const int N=1000050;
const long long Mod=1000000007;
using namespace std;
int a[30006], dp[30006][2], min_need[30006][2], record[30006][2];
int main() {
int t, n;
scanf("%d", &t);
rep(z, 0, t) {
scanf("%d", &n);
rep(i, 1, n+1) scanf("%d", &a[i]);
MEM(dp, 0x3f);
dp[0][1] = 0;
bool flag = 1;
rep(i, 1, n+1) {
# 如果右侧需要的流量大于容器容积
if (dp[i-1][1] > a[i]) {
flag = 0;
break;
}
# 左侧能够获取的流量，因为i-1从右侧获取的流量也会经过i，所以需要减去
dp[i][0] = min(dp[i-1][0], a[i] - dp[i-1][1]);
# 需要从右侧获取的流量需要累加
dp[i][1] = dp[i-1][1] + max(0, a[i] - dp[i][0] - dp[i-1][1]);
}
puts(flag ? "YES" : "NO");
}
return 0;
}
虽然这个是很简单的动态规划的思想，但是一些细节很容易忽略。比如说i-1位置的右侧流量会流经i以及大于i每一个位置。所以每一个位置的右侧流量是累加的，是越来越大的。只要能够把握住这点，AC是不难的。
总体来说这题的难度不大，对于思维的要求不是很高，但是非常考验思维的缜密性和逻辑性。非常适合用来进行思维锻炼。