?就是石子合并的數據范圍變為了1e3

經典四邊形優化區間dp

const int N = 2e3 + 10; const long long inf = 1e18; long long dp[N][N], sum[N]; int m[N][N], a[N];int main() {int T = 1;//T = read();while (T --){int n;n = read();for (int i = 1; i <= 2 * n; i ++){if (i <= n)a[i] = read();elsea[i] = a[i - n];m[i][i] = i;sum[i] = sum[i - 1] + a[i];}for (int len = 2; len <= n; len ++)for (int l = 1; l + len - 1 <= 2 * n; l ++){int r = l + len - 1;long long ans = inf;for (int k = m[l][r - 1]; k <= min(m[l + 1][r], r - 1); k ++)if (dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1] < ans){ans = dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1];m[l][r] = k;}dp[l][r] = ans;}long long ans = inf;for (int i = 1; i <= n; i ++)ans = min(ans, dp[i][i + n - 1]);cout << ans;}return 0; }

總結

以上是生活随笔為你收集整理的51nod 1022 石子合并v2的全部內容，希望文章能夠幫你解決所遇到的問題。

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