P1775 学习笔记

省流：弱化版还是太弱化了。

题目传送门

为什么叫弱化版呢？因为他是一个链，不是环！

这个区间 DP 还是比较经典的，先统计一下 AC 数量 前缀和

for (int i = 1; i <= n; i++)pre[i] = pre[i - 1] + a[i];

设 \(dp_{l,r}\) 表示合并区间 \([l,r]\) 的最小消耗。

还是的合并 \([i,i]\) 区间不需要消耗，即

for (int i = 1; i <= n; i++)dp[i][i] = 0;

这是取最小值，我们需要给 \(dp\) 数组赋一个极大值，即

memset(dp, 0x3f, sizeof(dp));

经典区间 DP 的转移方程还是比较好列的

\[dp_{l,r}=\min_{k=l}^{r-1} (dp_{l,k}+dp_{k+1,r}+pre[r]-pre[l-1]) \]

完事！

code

#include <bits/stdc++.h>
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;constexpr int mod = 998244353;
constexpr int maxn = 305;int n;int m[maxn], pre[maxn], dp[maxn][maxn];int main() {fast;cin >> n;memset(dp, 0x3f, sizeof(dp));for (int i = 1; i <= n; i++)cin >> m[i];for (int i = 1; i <= n; i++)pre[i] = pre[i - 1] + m[i];for (int i = 1; i <= n; i++)dp[i][i] = 0;for (int l = 2; l <= n; l++)for (int i = 1; i <= n - l + 1; i++){int j = i + l - 1;for (int k = i; k < j; k++)dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1]);}cout << dp[1][n];return 0;
}