【Educational Codeforces Round 58(Rated for Div.2)F.Trucks and Cities】DP+単調キュー最適化
25338 ワード
タイトルリンク
F. Trucks and Cities
に言及
n都市がx軸上にあり、m台のトラックがあり、各トラックには4つの属性があり、それぞれ開始都市s、終了都市f、1キロ当たり燃料消費c、および給油可能回数rである.給油トラックの油量が満タンになるたびに、トラックの油量はVで、すべてのトラックの初期油量は満タンになります.すべてのトラックを始点から終点までの最小油量Vを求める.
2 < = n < = 400 , 1 < = m < = 250000 2<=n<=400,1<=m<=250000 2<=n<=400,1<=m<=250000 1 < = a i < = 1 0 9 , a i < a i + 1 1<=a_i<=10^9,a_iまず暴力的なn 4 n^4 n 4のやり方を考えます.d p[i][j][k]dp[i][j][k]dp[i][j][k]をi i iからj j j休憩k回に到達する最小間隔とする.d p [ i ] [ j ] [ k ] = min j − 1 l = i + 1 ( max ( d p [ i ] [ l ] [ k − 1 ] , a [ j ] − a [ l ] ) ) dp\left[ i\right]\left[ j\right]\left[ k\right] =\underset{l=i+1}{\overset{j-1}{\min}}\left(\max\left( dp\left[ i\right]\left[ l\right]\left[ k-1\right] ,a\left[ j\right] -a\left[ l\right]\right)\right) dp[i][j][k]=l=i+1 minj−1(max(dp[i][l][k−1],a[j]−a[l]))コード
まず1次元をスクロールすることができ,その後max(d p[i][l][k−1],a[j]−a[l])maxleft(dpleft[iright]left[lright]left[lright],aleft[jright]−aleft[lright]right)max(dp[i][l][k−1],a[j]−a[l])これは決定の単調性を満たすことが分かった.単調なキューメンテナンスが必要で、複雑さはn 3 n^3 n 3になります.
コード#コード#
F. Trucks and Cities
に言及
n都市がx軸上にあり、m台のトラックがあり、各トラックには4つの属性があり、それぞれ開始都市s、終了都市f、1キロ当たり燃料消費c、および給油可能回数rである.給油トラックの油量が満タンになるたびに、トラックの油量はVで、すべてのトラックの初期油量は満タンになります.すべてのトラックを始点から終点までの最小油量Vを求める.
2 < = n < = 400 , 1 < = m < = 250000 2<=n<=400,1<=m<=250000 2<=n<=400,1<=m<=250000 1 < = a i < = 1 0 9 , a i < a i + 1 1<=a_i<=10^9,a_i
#include
",ans);
return 0;
}
まず1次元をスクロールすることができ,その後max(d p[i][l][k−1],a[j]−a[l])maxleft(dpleft[iright]left[lright]left[lright],aleft[jright]−aleft[lright]right)max(dp[i][l][k−1],a[j]−a[l])これは決定の単調性を満たすことが分かった.単調なキューメンテナンスが必要で、複雑さはn 3 n^3 n 3になります.
コード#コード#
#include
",ans);
return 0;
}