做网站优化的弊端,茶百道加盟费大概要多少,wordpress 调用文章简介,辽宁阜新建设学校官方网站problem
洛谷链接
solution
有一种 dpdpdp 并不常见。其主要思想大概就是积累后再支出 / 先预支后再填充。
本题就是积累后再支出。显然炮冷却好了后就一直处于可用状态#xff0c;玩没玩过游戏的都知道一冷却好就打一定不会劣于等一会再打#xff0c;因为这道题的炮也没…problem
洛谷链接
solution
有一种 dpdpdp 并不常见。其主要思想大概就是积累后再支出 / 先预支后再填充。
本题就是积累后再支出。显然炮冷却好了后就一直处于可用状态玩没玩过游戏的都知道一冷却好就打一定不会劣于等一会再打因为这道题的炮也没有射程限制。
我们可以很容易地设计出一个状态转移 dp:f[i][j]:dp:f[i][j]:dp:f[i][j]: 在第 iii 行 jjj 列时的最多冷却时间。
从状态设计来看。虽然是走到了障碍物才开炮减去冷却时间但在实际操作中一定是非常前面的某个冷却好的时刻开的炮远距离炸了这个障碍物。
有 f[i][j]max{min(f[i⊕1][j],t),f[i][j−1]1}f[i][j]\max\{\min(f[i\oplus 1][j],t),f[i][j-1]1\}f[i][j]max{min(f[i⊕1][j],t),f[i][j−1]1}。
换道之所以要跟 ttt 取 min\minmin是因为我们知道累计的时间都只能炸同行的后面障碍物一旦换道就非常现实一开始最多就积累武器冷却好的 ttt 秒多了的也不能用到不同的道。且要保证 f[i⊕1][j]f[i\oplus 1][j]f[i⊕1][j] 没有障碍物
不换道必须满足 f[i][j]f[i][j]f[i][j] 有障碍物的时候目前的积累时间能够射击一次。
到目前为止似乎可行但是很遗憾 nnn 的范围高达 1e91e91e9。根本开不出这么大的数组。
考虑一种换道的方式。假设现在在 (i,j)(i,j)(i,j)而 (i⊕1,j)(i\oplus 1,j)(i⊕1,j) 有障碍且现在要换道。
我是在 (i,j1)(i,j1)(i,j1) 时候就换道还是再走一段 (i,jk),k1(i,jk),k1(i,jk),k1 再换道。
显然是要换道就立马换。因为立即换道明显可以积累更多的可用时间。越晚换道积累的时间都是本道才可用的换道后能用的时间越少。
即在障碍物后要换道就直接换。
由此看来真正有用的关键点就是起点终点障碍物及障碍物后一个格子的位置。
就可以将 nnn 直接离散化压缩到 m1m2m_1m_2m1m2 的级别。
输出状态就要在转移的时候记录是否改为变道以便最后的路径倒推。
时间复杂度 O(m1m2)O(m_1m_2)O(m1m2)。
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[i1]-x[i]-1 的能量//-1是因为此时不能拿到x[i1]位置的一个能量//必须保证先能下一位置障碍物击破才能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;
}
