洛谷 P1880 [NOI1995]石子合并(区间DP)

嗯...

 

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

 

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

 

AC代码:

洛谷 P1880 [NOI1995]石子合并(区间DP)
 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代码

 

上一篇:leetcode 打家劫舍(动态规划)


下一篇:hdoj3534(树形dp,求树的直径的条数)