problem

洛谷鏈接

solution

有一種 $dp$ 并不常見。其主要思想大概就是積累后再支出 / 先預支后再填充。

本題就是積累后再支出。顯然炮冷卻好了后就一直處于可用狀態，玩沒玩過游戲的都知道一冷卻好就打一定不會劣于等一會再打，因為這道題的炮也沒有射程限制。

我們可以很容易地設計出一個狀態轉移 $dp:f[i][j]:$ 在第 $i$ 行 $j$ 列時的最多冷卻時間。

從狀態設計來看。雖然是走到了障礙物才開炮（減去冷卻時間），但在實際操作中一定是非常前面的某個冷卻好的時刻開的炮，遠距離炸了這個障礙物。

有 $f[i][j]=\max \{\min (f[i\oplus 1][j],t),f[i][j?1]+1\}$。

換道之所以要跟 $t$ 取 $\min$，是因為我們知道累計的時間都只能炸同行的后面障礙物，一旦換道就非常現實，一開始最多就積累武器冷卻好的 $t$ 秒，多了的也不能用到不同的道。且要保證 $f[i\oplus 1][j]$ 沒有障礙物，

不換道，必須滿足 $f[i][j]$ 有障礙物的時候，目前的積累時間能夠射擊一次。

到目前為止似乎可行，但是很遺憾 $n$ 的范圍高達 $1e9$。根本開不出這么大的數組。

考慮一種換道的方式。假設現在在 $(i,j)$，而 $(i\oplus 1,j)$ 有障礙，且現在要換道。

我是在 $(i,j+1)$ 時候就換道，還是再走一段 $(i,j+k),k>1$ 再換道。

顯然是要換道就立馬換。因為立即換道明顯可以積累更多的可用時間。越晚換道積累的時間都是本道才可用的，換道后能用的時間越少。

即在障礙物后要換道就直接換。

由此看來，真正有用的關鍵點就是起點，終點，障礙物及障礙物后一個格子的位置。

就可以將 $n$ 直接離散化壓縮到 $m_1+m_2$ 的級別。

輸出狀態就要在轉移的時候記錄是否改為變道，以便最后的路徑倒推。

時間復雜度 $O(m_1+m_2)$。

code

#include <bits/stdc++.h> using namespace std; #define maxn 2000005 vector < int > tran; vector < pair < int, int > > fire; int n, m1, m2, t, cnt; int x1[maxn], x2[maxn], x[maxn]; int f[2][maxn], g[2][maxn], p[2][maxn];int main() {scanf( "%d %d %d %d", &n, &m1, &m2, &t );for( int i = 1;i <= m1;i ++ ) {scanf( "%d", &x1[i] );x[++ cnt] = x1[i];x[++ cnt] = x1[i] + 1;}for( int i = 1;i <= m2;i ++ ) {scanf( "%d", &x2[i] );x[++ cnt] = x2[i];x[++ cnt] = x2[i] + 1;}x[++ cnt] = 0, x[++ cnt] = 0x7f7f7f7f; //將有用的關鍵點離散化sort( x + 1, x + cnt + 1 );cnt = unique( x + 1, x + cnt + 1 ) - x - 1;for( int i = 1;i <= m1;i ++ )p[0][lower_bound( x + 1, x + cnt + 1, x1[i] ) - x] = 1;for( int i = 1;i <= m2;i ++ )p[1][lower_bound( x + 1, x + cnt + 1, x2[i] ) - x] = 1;//標記有障礙坐標對應的離散化點memset( f, -1, sizeof( f ) );g[1][1] = 1, f[0][1] = f[1][1] = 0;//如果從第一行開始 就證明已經換車道了for( int i = 1;i <= cnt;i ++ ) {for( int k = 0;k <= 1;k ++ )if( ~ f[k][i] and ! p[k ^ 1][i] ) { //考慮換車道 要求另一車道沒有障礙if( f[k ^ 1][i] < min( f[k][i], t ) ) {f[k ^ 1][i] = min( f[k][i], t ); //最多只能儲存tg[k ^ 1][i] = 1; //=1 換車道記錄}}for( int k = 0;k <= 1;k ++ )if( ~ f[k][i] and f[k][i] + x[i + 1] - x[i] - 1 >= t * p[k][i + 1] ) {//不換車道考慮同車道的下一個關鍵點是否是障礙物//下一個關鍵點到當前關鍵還能再積累 x[i+1]-x[i]-1 的能量//-1是因為此時不能拿到x[i+1]位置的一個能量//必須保證先能下一位置障礙物擊破才能+1 所以下面+1就把-1抵消了if( f[k][i + 1] < f[k][i] + x[i + 1] - x[i] - t * p[k][i + 1] ) {f[k][i + 1] = f[k][i] + x[i + 1] - x[i] - t * p[k][i + 1];g[k][i + 1] = 0;}}}int px;if( f[0][cnt] < f[1][cnt] ) px = 1;else px = 0;if( ! ~f[px][cnt] ) return ! printf( "No\n" );else printf( "Yes\n" );int py = cnt, now = 0x3f3f3f3f;while( px or py > 1 ) {if( g[px][py] ) {tran.push_back( x[py] );px ^= 1;}else {if( p[px][py] ) {now = min( now - t, x[py] - 1 );//因為是倒著推操作方案 所以now是后一個機器最晚必須射擊的時間//now-t就是為了正著時后面的障礙物著想//只有這個時候射擊 才能給機器足夠的冷卻時間去設計更后面的障礙物fire.push_back( make_pair( now, px + 1 ) );}py --;}}printf( "%d\n", tran.size() );for( int i = tran.size() - 1;~ i;i -- ) printf( "%d ", tran[i] );printf( "\n%d\n", fire.size() );for( int i = fire.size() - 1;~ i;i -- ) printf( "%d %d\n", fire[i].first, fire[i].second );return 0; }

總結

以上是生活随笔為你收集整理的CF936D World of Tank（思维dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。