圓環取數 jzoj1397 dp ST

NO IMAGE

Description


  小K攢足了路費來到了教主所在的宮殿門前,但是當小K要進去的時候,卻發現了要與教主守護者進行一個特殊的遊戲,只有取到了最大值才能進去Orz教主……

  守護者拿出被劃分為n個格子的一個圓環,每個格子上都有一個正整數,並且定義兩個格子的距離為兩個格子之間的格子數的最小值。環的圓心處固定了一個指標,一開始指向了圓環上的某一個格子,你可以取下指標所指的那個格子裡的數以及與這個格子距離小於k的格子的數,取一個數的代價即這個數的值。指標是可以轉動的,每次轉動可以將指標由一個格子轉向其相鄰的格子,且代價為圓環上還剩下的數的最大值。
  現在對於給定的圓環和k,求將所有數取完所有數的最小代價。

Solution


首先每個數字最終都是要拿走的,那麼取走所有數字的費用其實是固定的,貪心地講任何時候拿走全部數字都是最優的,那麼破環成鏈做

只考慮指標的移動,那麼就是一個比較簡單的區間dp了
f[i][j][0/1]f[i][j][0/1]分別表示從左取i個從右取j個指標停留在左邊/右邊的最小費用,依照慣例第一維是可以滾的。轉移見程式
區間的最大值可以暴力打表預處理,也可以ST一下,為了卡到第一名這裡用了ST (結果還是沒有第一名快)

考試的時候沒有考慮完整的轉移,寫的暴力還掛了(哭泣

Code


#include <stdio.h>
#include <string.h>
#include <math.h>
#define rep(i, st, ed) for (int i = st; i <= ed; i  = 1)
#define fill(x, t) memset(x, t, sizeof(x))
#define min(x, y) (x)<(y)?(x):(y)
#define max(x, y) (x)>(y)?(x):(y)
#define INF 0x3f3f3f3f
#define N 2001
int maxF[N][15], t[N], f[2][N][2];
inline int query(int x, int y){
if (x > y){
return 0;
}
int v = (int)(log2(y - x   1));
return max(maxF[x][v],maxF[y - (1 << v)   1][v]);
}
int main(void){
int n, m;
scanf("%d%d", &n, &m);
int tot = 0;
rep(i, 1, n){
scanf("%d", &t[i]);
maxF[i][0] = t[i];
tot  = t[i];
}
rep(j, 1, 13){
for (int i = 1; i <= n && i   (1 << j) - 1 <= n; i   ){
maxF[i][j] = max(maxF[i][j - 1], maxF[i   (1 << (j - 1))][j - 1]);
}
}
int ans = INF;
rep(i, 0, n){
rep(j, 0, n - i){
if (!i && !j){
continue;
}
if (j > 0){
int mx = query(i   m   2, n - m - j   1);
f[i & 1][j][1] = min(f[i & 1][j - 1][1]   mx, f[i & 1][j - 1][0]   mx * (i   j));
}else{
f[i & 1][j][1] = INF;
}
if (i > 0){
int mx = query(i   m   1, n - m - j);
f[i & 1][j][0] = min(f[(i - 1) & 1][j][0]   mx, f[(i - 1) & 1][j][1]   mx * (i   j));
}else{
f[i & 1][j][0] = INF;
}
if (i   j == n){
ans = min(ans, f[i & 1][j][0]);
ans = min(ans, f[i & 1][j][1]);
}
}
}
printf("%d\n", tot   ans);
return 0;
}