//其实是个伪单调队列...渣渣刚入门
//戳这里：
//dp[ i ][ j(现身高) ] = min( dp[ i ][ k(现身高) ] + fabs( j(现身高) - k(现身高) ) * C + （ j(现身高) - h[i](原身高) ) *（ j(现身高) - h[i](原身高) ) );
观察到可以单调队列优化，O(N * H * H) —> O(N * H)
j >= k 时，
dp[ i ][ j ] = min ( dp[ i - 1 ][ k ] + ( j - k ) * C + ( j - h[i] ) * ( j - h[i] ) ); <==> dp[ i ][ j ] = min ( dp[ i - 1][ k ] - k * C ) + j * C + ( j - h[i] ) * ( j - h[i] );
j <= k 时，
dp[ i ][ j ] = min ( dp[ i - 1 ][ k ] + ( k - j ) * C + ( j - h[i] ) * ( j - h[i] ) ); <==> dp[ i ][ j ] = min ( dp[ i - 1 ][ k ] + k * C ) - j * C + ( j - h[i] ) * ( j - h[i] );
将 k 替换成 j, 实现一边维护 dp_pre, 一边求解 dp[ i ][ j ]
1 #include "bits/stdc++.h" 2 using namespace std; 3 int N, C; 4 int h[50010]; 5 int dp[50010][110]; 6 const int INF = 0x3f3f3f3f; 7 8 int main() 9 {10 while(scanf("%d%d", &N, &C) != EOF) {11 memset(dp, INF, sizeof(dp[0]) * (N + 1)); //直接 memset(dp, INF, sizeof(dp)); 会T...12 int i;13 for(i = 1; i <= N; ++i) {14 scanf("%d", &h[i]);15 }16 int j, k;17 for(j = h[1]; j <= 100; ++j) {18 dp[1][j] = (j - h[1]) * (j - h[1]);19 }20 21 int dp_pre;22 for(i = 2; i <= N; ++i) {23 //k <= j 的情况24 dp_pre = INF;25 for(j = h[i - 1]; j <= 100; ++j) {26 dp_pre = min(dp_pre, dp[i - 1][j] - j * C);27 if(j >= h[i]) {28 dp[i][j] = dp_pre + j * C + (j - h[i]) * (j - h[i]);29 }30 }31 32 //k >= j 的情况33 dp_pre = INF;34 for(j = 100; j >= h[i]; --j) {35 if(j >= h[i - 1]) {36 dp_pre = min(dp_pre, dp[i - 1][j] + j * C);37 }38 dp[i][j] = min(dp[i][j], dp_pre - j * C + (j - h[i]) * (j - h[i]));39 }40 }41 int res = INF;42 for(j = 1; j <= 100; ++j) {43 res = min(res, dp[N][j]);44 }45 printf("%d\n", res);46 }47 }