洛谷 P1880 [NOI1995]石子合并（区间DP）

淡淡的烟草味﹌ 2023-06-04 13:57 96阅读 0赞

嗯...

题目链接：https://www.luogu.org/problem/P1880

这道题特点在于石子是一个环，所以让a\[i+n\] = a\[i\]（两倍长度）即可解决环的问题，然后注意求区间最小值的时候dp要初始化为一个很大的数...

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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代码

转载于:https://www.cnblogs.com/New-ljx/p/11569196.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/01fa5a13c15e46f08767fdf67b3f904d.png