3 条题解
-
0
#include <vector> #include <climits> using namespace std; int main() { int n; cin >> n; vector<int> a(2 * n); for (int i = 0; i < n; ++i) { cin >> a[i]; a[i + n] = a[i]; // 处理环形数组 } // 计算前缀和数组 vector<long long> prefix(2 * n + 1, 0); for (int i = 1; i <= 2 * n; ++i) { prefix[i] = prefix[i - 1] + a[i - 1]; } // 初始化动态规划数组 const long long INF = 1e18; vector<vector<long long> > dp_min(2 * n, vector<long long>(2 * n, INF)); vector<vector<long long> > dp_max(2 * n, vector<long long>(2 * n, -INF)); for (int i = 0; i < 2 * n; ++i) { dp_min[i][i] = 0; dp_max[i][i] = 0; } // 动态规划填表 for (int len = 2; len <= n; ++len) { // 合并的区间长度 for (int i = 0; i <= 2 * n - len; ++i) { // 区间起点 int j = i + len - 1; // 区间终点 long long sum_ij = prefix[j + 1] - prefix[i]; // 枚举分割点k for (int k = i; k < j; ++k) { dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum_ij); dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum_ij); } } } // 寻找所有可能的起点中的最优解 long long min_score = INF, max_score = -INF; for (int i = 0; i < n; ++i) { int j = i + n - 1; min_score = min(min_score, dp_min[i][j]); max_score = max(max_score, dp_max[i][j]); } cout << min_score << endl; cout << max_score << endl; return 0; }
没见过吧,那就点赞再走。
求求了QAQ
-
0
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <iomanip> #include <cmath> #include <queue> #include <map> #include <stack> #include <vector> using namespace std; #define long long LL const int N = 1e3+5; const int INF = 0x3f3f3f3f; int n,a[N],dp[N][N],minn = INF,sum[N],dp1[N][N],maxx; int main(){ cin >> n; memset(dp,INF,sizeof(dp)); for (int i = 1;i<=n;i++){ cin >> a[i]; a[i+n] = a[i]; } for (int i = 1;i<=2*n;i++){ sum[i] = sum[i-1] + a[i]; dp[i][i] = 0; } for (int i = 2;i<=n;i++){ for (int j = 1;j<=2*n-i+1;j++){ int endx = j + i - 1; for (int k = j;k<endx;k++){ dp[j][endx] = min(dp[j][endx],dp[j][k] + dp[k+1][endx] + sum[endx] - sum[j-1]); dp1[j][endx] = max(dp1[j][endx],dp1[j][k] + dp1[k+1][endx] + sum[endx] - sum[j-1]); } } } for (int i = 1;i<=n;i++){ minn = min(minn,dp[i][i+n-1]); maxx = max(maxx,dp1[i][i+n-1]); } cout << minn << endl << maxx; return 0; }
-
0
'''和上一题十分类似,简单加点东西就好了。这里不多做解释。代码比较好理解。
/***************************************** 备注: ******************************************/ #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; int n; int dp[505][505]; int f[505][505]; int a[305]; int sum[N]; int main(){ cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; a[i + n] = a[i]; } for(int i=1; i<=2*n; i++) { sum[i] = sum[i - 1] + a[i]; } for(int k = 2; k <= n; k++) { for(int l = 1; l + k - 1 <= 2 * n; l++) { int r = l + k - 1; f[l][r] = INF; for(int i = l; i < r; i++) { dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r] + sum[r] - sum[l - 1]); f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r] + sum[r] - sum[l - 1]); } } } int minn = INF; int maxx = 0; for(int i = 1; i <= n; i++) { maxx = max(maxx, dp[i][i + n - 1]); minn = min(minn, f[i][i + n - 1]); } cout<<minn<<endl; cout<<maxx<<endl; return 0; }
- 1
信息
- ID
- 1639
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 157
- 已通过
- 64
- 上传者