嗯...
题目链接:https://www.luogu.org/problem/P1880
这道题特点在于石子是一个环,所以让a[i+n] = a[i](两倍长度)即可解决环的问题,然后注意求区间最小值的时候dp要初始化为一个很大的数...
AC代码:
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 6 using namespace std; 7 8 int dp1[205][205], dp2[205][205], sum[205], a[205]; 9 10 int main(){ 11 int n; 12 scanf("%d", &n); 13 for(int i = 1; i <= n; i++) {scanf("%d", &a[i]); a[i + n] = a[i];} 14 for(int i = 1; i <= n * 2; i++) {sum[i] = sum[i - 1] + a[i];} 15 for(int l = 1; l <= n; l++){ 16 for(int i = 1; i <= 2 * n; i++){ 17 int j = i + l; 18 dp2[i][j] = 0x3f3f3f;// 求最小值初始化为很大 19 if(j > 2 * n) break; 20 for(int k = i; k < j; k++){ 21 dp1[i][j] = max(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + sum[j] - sum[i - 1]); 22 dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + sum[j] - sum[i - 1]); 23 } 24 } 25 } 26 int maxx = 0, minn = 0x3f3f; 27 for(int i = 1; i <= n; i++){ 28 int j = i + n - 1; 29 maxx = max(maxx, dp1[i][j]); 30 minn = min(minn, dp2[i][j]); 31 } 32 printf("%d\n%d\n", minn, maxx); 33 return 0; 34 }AC代码