洛谷的刷题日常之P1880

 Algorithm
 

石子合并

先看一道比luogu p1880简单的题目。

  • 描述：

有n堆石子排成一排，每堆石子有一定的数量，将n堆石子合并成一堆。合并的规则是每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数。石子经过n-1次合并后成为一堆，求总的最小花费和最大花费。

  • 输入：

有多组测试数据，输入到文件结束。每组测试数据的第1行有一个整数n，表示有n堆石子，n<250。接下来的一行有n个数，分别表示这n堆石子的数目。每堆石子至少一颗，最多10000颗。

  • 输出：

总的最小花费和最大花费。

  • 输入样例：

3
2 4 5

  • 输出样例：

17
20

  • 解题思路：区间DP

  • 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

const int INF=1<<30;
const int N=300;
int n,sum[N];

int Minval(){
    int dp[N][N]；
    for(int i=1;i<=n;i++) dp[i][i]=0;
    for(int len=1;len<n;len++)
        for(int i=1;i<=n-len;i++) {
            int j=i+len;
            dp[i][j]=INF;
            for(int k=i;k<j;k++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
        }
    return dp[1][n];
}
int Maxval(){
    int dp[N][N];
    for(int i=1;i<=n;i++) dp[i][i]=0;
    for(int len=1;len<n;len++)
        for(int i=1;i<=n-len;i++) {
            int j=i+len;
            dp[i][j]=-INF;
            for(int k=i;k<j;k++)
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
        }
    return dp[1][n];
}
int main() {
    scanf("%d",&n);
    sum[0]=0;
    for(int i=1;i<=n;i++) {
        int x;
        scanf("%d",&x);
        sum[i]=sum[i-1]+x;
    }
    printf("%d\n%d",Minval(),Maxval());
    return 0;
}

环形石子合并

接下来就可以着手解决luogu p1880了。如果按照上面的解法解这道题，会出现“min值永远比正确答案大1”的“奇怪”现象，这是因为没有考虑环形的缘故。

  • 描述：

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

  • 输入：

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

  • 输出：

输出共2行,第1行为最小得分,第2行为最大得分.

  • 输入样例：

4
4 5 9 4

  • 输出样例：

43
54

  • 解题思路：

    • 区间DP
    • 处理环形情况的通用套路：在任意位置把环断开成链，复制一倍接在末尾

  • 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;

const int INF=1<<30;
const int N=240;
int n,sum[N],x,arr[N];

int Minval(){
    int dp[N][N],ans=INF;
    for(int i=1;i<=n;i++) dp[i][i]=0;
    for(int len=1;len<n;len++)
        for(int i=1;i<=2*n-len;i++) {
            int j=i+len;
            dp[i][j]=INF;
            for(int k=i;k<j;k++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
        }
    for(int i=1;i<=n;i++) {
        ans=ans>dp[i][i+n-1]?dp[i][i+n-1]:ans;
    }
    return ans;
}
int Maxval(){
    int dp[N][N],ans=-INF;
    for(int i=1;i<=n;i++) dp[i][i]=0;
    for(int len=1;len<n;len++)
        for(int i=1;i<=2*n-len;i++) {
            int j=i+len;
            dp[i][j]=-INF;
            for(int k=i;k<j;k++)
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
        }
    for(int i=1;i<=n;i++) {
        ans=ans<dp[i][i+n-1]?dp[i][i+n-1]:ans;
    }
    return ans;
}
int main() {
    scanf("%d",&n);
    sum[0]=0;
    for(int i=1;i<=n;i++) {
        scanf("%d",&arr[i]);
        arr[i+n]=arr[i];
    }
    for(int i=1;i<=2*n;i++) {
        sum[i]=sum[i-1]+arr[i];
    }
    printf("%d\n%d",Minval(),Maxval());
    return 0;
}
  • 相似题目：

hdu 3506 “Monkey Party”

 Previous

Number theory Greedy