雖然是簡單的dp ，but真的太難想到了，而且我的碼力。。。

Train Tracking 2

【題目描述】
每天特快列車都會經(jīng)過農(nóng)場。列車有N節(jié)車廂（1≤N≤10^{5），每節(jié)車廂上有一個1到10}9之間的正整數(shù)編號；不同的車廂可能會有相同的編號。 平時，Bessie會觀察駛過的列車，記錄車廂的編號。但是今天霧實在太濃了，Bessie一個編號也看不見！幸運的是，她從城市里某個可靠的信息源獲知了列車編號序列的所有滑動窗口中的最小值。具體地說，她得到了一個正整數(shù)K，以及N?K+1個正整數(shù)c1,…,cN+1?K，其中ci是車廂i,i+1,…,i+K?1之中編號的最小值。

幫助Bessie求出滿足所有滑動窗口最小值的對每節(jié)車廂進行編號的方法數(shù)量。由于這個數(shù)字可能非常大，只要你求出這個數(shù)字對10^9+7取余的結(jié)果Bessie就滿意了。

Bessie的消息是完全可靠的；也就是說，保證存在至少一種符合要求的編號方式。

【輸入輸出格式】
輸入的第一行包含兩個空格分隔的整數(shù)N和K。余下的行包含所有的滑動窗口最小值c1,…,cN+1?K，每行一個數(shù)。

輸出一個整數(shù)：對每節(jié)車廂給予一個不超過109的正整數(shù)編號的方法數(shù)量對10^9+7取余的結(jié)果，滿足車廂i,i+1,…,i+K?1之中編號的最小值等于ci，對于1≤i≤N?K+1均成立。

【輸入輸出樣例】
輸入
4 2
999999998
999999999
999999998
輸出
3
【分析】
1：999999998 999999999 999999999 999999998
2：999999998 999999999 1000000000 999999998
3：999999998 1000000000 999999999 999999998

【解題思路】
首先你嘚想到相鄰的$i，j$如果它們的最小值不一樣，那么一定可以固定一個點

eg：$i$到$i+k?1$的最小值$4,j$到$j+k?1$的最小值$3$，$i$小于$j$，即$j=i+1$，這個時候就固定了$j+k?1$得是$3$

從中我們的啟發(fā)是什么

把c值相同的連續(xù)區(qū)間單獨拎出來

$ci=ci+1=ci+2=...=cj=v$

這一段代表的區(qū)間總長為$j?i+k$，證明一下：$i$到$j$區(qū)間長為$j?i+1$沒問題

那么$j$包含的區(qū)間長是$k$，加在一起再減去一個重復(fù)的$j$就是$j?i+k$，繼續(xù)

所有的數(shù)都大于等于$v$，同時每$k$個中就有至少一個$v$

有一個直接的dp：設(shè)$dp[i]$表示最后一個$v$在$i$位置時的合法方案數(shù)，$p$為$1e9?v$

那么有轉(zhuǎn)移$dp[i]=\sum （j=i?k，i?1）p^i?j?1?f[j]$

這樣是$O(nk)$的，會TLE

稍微改變一下錯位相消就變成了：

dp[i]=(p+1)*f[i?1]?p^k?f[i?k?1]

在這里要解釋一下首先如果有最小值是$x$，那么方案數(shù)就是$(1e9?x+1{)}^{j?i+1}$減去不合法的方案數(shù)

在$[i，j]$區(qū)間不合法的方案數(shù)其實是所有取值全都大于了$v$，沒有一個是$v$，其實也就是$(1e9?x+1{)}^{j?i+1}$

問題是為什么要乘以$dp[i?k?1]$呢？

你想想在$i$不合法的方案數(shù)，在$i?1$時是屬于合法的方案數(shù)，所以影響$i$的是$i?k?1$的所有方案
因為從$i?k?1$開始往前不管選什么都與$i$無關(guān)，所以后面是不合法的，前面不管合不合法都算不合法，所以要相乘

接著就是考慮如何處理兩個$v$不一樣的交界處
說白了就是兩個$v$誰更大，相交的部分就交給誰處理
因為這就好比不等式解集的取法，如果這個香蕉區(qū)間既要滿足最小值為5又要滿足最小值為6那坑定是選滿足最小值為6啊！

如果處理到$i$時，$i$有一部分區(qū)間被前面處理過，那么就要減去$k$

因為我們是循環(huán)$i$是每次只加$1$所以當(dāng)最小值不一樣的時候，兩個區(qū)間的香蕉部分就是$k?1$，又因為這$k?1$被前面處理過，也就意味著$i$這個點為了滿足最小值也是固定的，那么真正波動的有選擇的長度就減去了$k$

同理如果處理到$i$時，發(fā)現(xiàn)$i+1$的最小值更大，也就意味著有$k?1$區(qū)間是后面處理，i也固定下來了。長度便又減去了$k$

最后就是注意頭$i=1$和尾$i=n?k+1$時的特判，如果$i=1$它就不能進行把$k?1$區(qū)間交給前面的人處理，因為它前面沒人；如果$i=n?k+1$它就不能進行把$k?1$區(qū)間交給后面的人處理，因為它后面也沒人了。

在這里，要重點解釋一下下面代碼的dp初值設(shè)定，早上吃飯時突然靈機乍現(xiàn)，明白這樣寫的原因

為什么？dp[0]和dp[1]初值是1 為什么？window里i循環(huán)要從2開始
1）dp[0]的情況，就是這一段區(qū)間剛好就是1~k，
那么當(dāng)我們算到dp[k]的時候，它是包含了從1~k所有都取大于min的值的不合法的方案數(shù)
而我們要減掉這些不合法的方案數(shù)，也就是每一個數(shù)的取值都是min+1~1e9，有k個
所以不合法方案數(shù)就是（1e9-(min-1)+1）^k也就是代碼中的tp，
那么這個系數(shù)是由dp[0]來提供，因而要賦值成1

2）dp[1]的情況，就是這一段區(qū)間剛好是1~k+1
而我們能進入這個函數(shù)一定要滿足這個區(qū)間所有數(shù)的最小值是一樣的val
所以當(dāng)我們算到dp[k+1]的時候
不合法的方案數(shù)=2~k全都不是最小值方案數(shù)*dp[1]的方案數(shù)
那dp[1]不應(yīng)該是tp嗎？
no~~因為我們的通向dp式dp[i-k-1]是乘以(1e9-min)的K次方，而2到k全都不是最小值方案數(shù)是(1e9-min)的K-1次方，dp[1]的所有方案數(shù)是（1e9-min）相乘剛好就是k次方
那么這時候的系數(shù)又是由dp[1]提供的，就只能賦值成1

同樣這也是為什么我們的i是從2開始循環(huán)，為了考慮這兩種情況就要給0，1騰位置，

【代碼實現(xiàn)】

#include <cstdio> const int mod = 1e9 + 7; const int p = 1e9; #define MAXN 100005 #define LL long long int n, k; LL c[MAXN]; LL result = 1; LL dp[MAXN];LL qkpow ( LL x, LL y ) {LL res = 1;while ( y ) {if ( y % 2 ) res = ( res * x ) % mod;x = ( x * x ) % mod;y >>= 1;}return res % mod; }LL window ( LL val, LL len ) {LL tmp = p - val;LL tp = qkpow ( tmp, k );dp[0] = dp[1] = 1;for ( int i = 2;i <= len + 1;i ++ ) {dp[i] = ( ( tmp + 1 ) * dp[i - 1] ) % mod;if ( i - k - 1 >= 0 ) dp[i] = ( ( dp[i] - ( ( tp * dp[i - k - 1] ) % mod ) + mod ) % mod ) % mod;}return dp[len + 1] % mod; }int main() {scanf ( "%d %d", &n, &k );for ( int i = 1;i <= n - k + 1;i ++ )scanf ( "%lld", &c[i] );for ( int i = 1, j;i <= n - k + 1;i = j + 1 ) {LL len;j = i;while ( c[i] == c[j + 1] )j ++;len = j - i + k;if ( i != 1 && c[i - 1] > c[i] )len -= k;if ( j != n - k + 1 && c[j + 1] > c[i] )len -= k;if ( len > 0 )result = ( result * window ( c[i], len ) ) % mod;}printf ( "%lld", result % mod );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[USACO19JAN,Platinum]Train Tracking 2的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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