P1880 学习笔记

省流：加个环至于绿吗？

题目传送门

看到环——断环为链，即

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

这题就是加了一个环和一个最大值，其他都没啥区别，参见 弱化版学习笔记

最后放一个 AC code

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 = 205;int n, x, y, ans1 = INT_MAX, ans2 = INT_MIN; // 赋初值啊int a[maxn][maxn], dp1[maxn][maxn], dp2[maxn][maxn];int main() {fast;freopen("std.in", "r", stdin);freopen("std.out", "w", stdout);cin >> n;for (int i = 1; i <= n; i++)cin >> a[i][i];for (int i = 1; i <= n; i++)a[n + i][n + i] = a[i][i]; // 断环为链for (int i = 2; i <= n; i++)for (int j = 1; j <= 2 * n - i + 1; j++){x = j, y = i + j - 1;for (int k = 1; k < i; k++){a[x][y] = a[x][x + k - 1] + a[x + k][y];if (dp1[x][y] != 0) // 被使用过dp1[x][y] = min(dp1[x][y], a[x][y] + dp1[x][x + k - 1] + dp1[x + k][y]);else // 否则直接赋值，不然的话全是 0dp1[x][y] = a[x][y] + dp1[x][x + k - 1] + dp1[x + k][y];if (dp2[x][y] != 0)dp2[x][y] = max(dp2[x][y], a[x][y] + dp2[x][x + k - 1] + dp2[x + k][y]);else dp2[x][y] = a[x][y] + dp2[x][x + k - 1] + dp2[x + k][y];} // 其实上面的操作你也可以使用类似给 dp 数组赋一个极大值和极小值的操作，就可以省去 if}for (int i = 1; i <= n - 1; i++)ans1 = min(ans1, dp1[i][n + i - 1]); // 求答案for (int i = 1; i <= n - 1; i++)ans2 = max(ans2, dp2[i][n + i - 1]); // 求答案cout << ans1 << endl << ans2; // 快乐输出return 0;
}