題意

給定n個整數(shù)，對于這n個整數(shù)我們可以采取兩種操作。第一種操作是在數(shù)組左側(cè)選擇連續(xù)的k個整數(shù)減1，第二種操作是選擇右側(cè)的連續(xù)k個整數(shù)減1。

比如假設(shè)數(shù)組是[3, 2, 2, 1, 4]，比如我們選擇k=2，取最左側(cè)進行操作，那么我們會得到[2, 1, 2, 1, 4]。如果我們選擇k=3，再取右側(cè)進行操作，可以得到[2, 1, 1, 0, 3]。

現(xiàn)在我們想要知道，給定這樣的數(shù)組，我們能否通過這兩個操作將數(shù)組清空。如果可以輸出YES，否則的話輸出NO。

樣例

首先輸入一個整數(shù)t（），表示測試數(shù)據(jù)組數(shù)。

對于每組測試數(shù)據(jù)，首先輸入一個整數(shù)n（），表示數(shù)組當(dāng)中元素的個數(shù)。之后輸入一行整數(shù)（）。可以保證，每一組測試數(shù)據(jù)的n之和不會超過30000.

題解

由于我們對于k沒有限制，最多我們可以一次對數(shù)組內(nèi)的n個元素全部減一。所以k不是限制我們的因素，最大的限制其實是在元素本身。

我們分析一下會發(fā)現(xiàn)，由于數(shù)組當(dāng)中的元素大小不一，這其實是隱形的限制。舉個例子，比如[2, 8, 3]。由于我們只能從兩側(cè)開始選擇元素進行操作，所以由于2和3比較小，會導(dǎo)致我們沒有辦法把中間的8消除完。當(dāng)然無法消除的原因可能有好幾種，但基本上都是由于元素的大小不一導(dǎo)致的。

首先我們對這個問題進行一個簡單的建模，題目當(dāng)中沒有限制執(zhí)行的次數(shù)，所以減一次和減很多次是一樣的。我們可以把可以合并的操作合并在一起，理解成執(zhí)行一次可以減去任意的值。并且我們可以把操作反向理解，把數(shù)組當(dāng)中的值看成是容器，這樣我們從數(shù)組當(dāng)中減去值的操作，就可以等價理解成向容器當(dāng)中輸入水流，這樣會容易理解一些。

我的第一想法很簡單，我們可以求出每個位置能夠從左側(cè)和右側(cè)分別獲得的最大數(shù)值。只要左右兩側(cè)能夠獲取的流量之和大于等于容器的容積，那么就說明我們可以獲取到足夠的流量灌滿所有的容器。

我很快就寫出了代碼，建了一個二維數(shù)組，dp[i][0]表示第i個元素從左側(cè)源頭能夠獲取的最大流量。dp[i][1]表示第i個元素可以從右側(cè)源頭獲取到的最大流量。由于我們需要保證每個容器存儲的體積不能超過容量，所以我們需要很容易得出遞推關(guān)系。

dp[i][0] = min(dp[i-1][0], a[i])

關(guān)系明確了很容易寫出代碼：

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);// 從左側(cè)遞推，獲取dp[i][0]rep(i, 1, n+1) {dp[i][0] = min(dp[i-1][0], a[i]);}// 從右側(cè)遞推，獲取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) {// 如果存在某個元素從左右兩側(cè)獲取的流量之和無法灌滿// 則返回NOif (dp[i][0] + dp[i][1] < a[i]) {flag = 0;break;}}puts(flag ? "YES" : "NO");}return 0; }

但是很遺憾，這樣不能AC，因為dp的數(shù)組維護的其實是某個位置從左側(cè)和從右側(cè)能夠獲取的最大值，這是一個理想情況，很有可能這個理想情況是無法實現(xiàn)的。

舉個很簡單的反例：[2, 4, 2, 4, 2]，這些元素左右兩邊能夠獲取到的最大流量值都是2，但是這里是有問題的。觀察一下會發(fā)現(xiàn)數(shù)組當(dāng)中的兩個4是無法同時滿足的，無法滿足的原因是因為中間的2限制了通過的流量。雖然理論上從左往右和從右往左能夠通過的流量上限都是2，但是這個上限是無法同時取到的。

這個問題用上述的方法是解決不了的，所以需要重新構(gòu)思。這里我們深入分析會發(fā)現(xiàn)一個比較麻煩的點，在于每個點都有兩個源頭，我們無法確定流量分配。不過這個問題也很好解決，因為左右兩邊的流量是沒有區(qū)別的。所以我們可以以某一側(cè)為主，剩余不夠的流量再由另一側(cè)補充。

比如我們可以以左側(cè)為主，把左側(cè)能夠獲取的流量開啟到最大，不夠地再通過右側(cè)補充。如果右側(cè)的流量無法補充，那么就說明無解。

我們用dp[i][0]記錄i位置從左側(cè)獲取的流量，dp[i][1]記錄i位置從右側(cè)獲取的流量。

#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) {# 如果右側(cè)需要的流量大于容器容積if (dp[i-1][1] > a[i]) {flag = 0;break;}# 左側(cè)能夠獲取的流量，因為i-1從右側(cè)獲取的流量也會經(jīng)過i，所以需要減去dp[i][0] = min(dp[i-1][0], a[i] - dp[i-1][1]);# 需要從右側(cè)獲取的流量需要累加dp[i][1] = dp[i-1][1] + max(0, a[i] - dp[i][0] - dp[i-1][1]);}puts(flag ? "YES" : "NO");}return 0; }

雖然這個是很簡單的動態(tài)規(guī)劃的思想，但是一些細(xì)節(jié)很容易忽略。比如說i-1位置的右側(cè)流量會流經(jīng)i以及大于i每一個位置。所以每一個位置的右側(cè)流量是累加的，是越來越大的。只要能夠把握住這點，AC是不難的。

總體來說這題的難度不大，對于思維的要求不是很高，但是非常考驗思維的縝密性和邏輯性。非常適合用來進行思維鍛煉。

總結(jié)

以上是生活随笔為你收集整理的牛客网-数据结构笔试题目（五）-动态规划问题求解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。