大家好，歡迎來到codeforces專題。
今天選擇的問題是1443場次的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。
樣例
首先輸入一個整數t（
），表示測試資料組數。
對于每組測試資料，首先輸入一個整數n（
），表示數組當中元素的個數。之後輸入一行整數
（
）。可以保證，每一組測試資料的n之和不會超過30000.
題解
由于我們對于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是不難的。
總體來說這題的難度不大，對于思維的要求不是很高，但是非常考驗思維的缜密性和邏輯性。非常适合用來進行思維鍛煉。
今天的文章就到這裡，衷心祝願大家每天都有所收獲。如果還喜歡今天的内容的話，請來一個三連支援吧~（點贊、關注、轉發）