迷你滨

用户名：uq_20629230267

访问量：8707

签　名：

等　　级
排　　名	2251
经　　验	2301
参赛次数	0
文章发表	13
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2023年第十四届省赛JavaB- C 数组分割（逆元+组合数）
浏览：725

蓝桥杯2023年第十四届省赛JavaB -买二赠一（贪心＋二分）
浏览：534

蓝桥杯2023年第十四届省赛真题JavaB-蜗牛（线性dp）
浏览：1156

你可能喜欢

蓝桥杯2023年第十四届省赛真题-合并石子（区间dp）

　　作者: 迷你滨　　　　发表时间：2023-04-27 14:07:25 浏览：838　|　评论：2　

原题链接：蓝桥杯2023年第十四届省赛真题-合并石子

### 蓝桥杯2023年第十四届省赛真题-合并石子（区间dp）
***
石子合并裸题。

设 $$dp[i][j][col]$$ 为 合并区间 $$[i,j]$$ 为一堆，且颜色为 $$col$$ 的最小花费，有转移式：

dp[i][j][(col+1)%3] = min(dp[i][j][(col+1)%3],dp[i][k][col]+dp[k+1][j][col]+sum[i][j])

其中 $$sum[i][j]$$ 为区间 $$[i,j]$$ 内石子总数。

为统计最小堆数，设$$num[i][j]$$为操作合并区间$$[i,j]$$后的最小堆数，初始化为区间长度；更新$$dp[i][j]$$的同时，更新$$num[i][j]=1$$，即合并为1堆。

为统计总共最小花费，设为$$cost[i][j]$$，初始化 $$[i,j]$$区间能合并为一堆的花费为$$min(dp[i][j][col])$$，其他不能合并为1堆的花费初始化为0（因为没有合并，就不用花费），然后用类似$$floyd$$的算法转移即可。
复杂度：$$O(3*n^3)$$
```Java
import java.io.*;
import java.util.*;
public class Main{
    static int maxn = 200005,n,m,inf=(int)1e9;
    static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
    static Scanner sc = new Scanner (System.in);
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st  =new StreamTokenizer(bf);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[]args) throws IOException{
        int T = 1;
        while(T-->0) solve();
        pw.flush();
    }
    static final int I() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    static int dp[][][] = new int [303][303][3];
    static int num[][] = new int [303][303];
    static int a[] = new int [301];
    static int sum[] = new int [301]; //前缀和
    static int c[] = new int [301];
    static int cost[][] = new int [303][303];
    static void solve() throws IOException{
        n= I();
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++) {
                num[i][j]=j-i+1;
                for(int k=0;k<3;k++) dp[i][j][k]=inf;
            }
        for(int i=1;i<=n;i++) {
            a[i] = I();
            sum[i]=a[i]+sum[i-1]; //前缀和，方便统计区间
        }
        for(int i=1;i<=n;i++) {
            c[i] = I();//颜色
            dp[i][i][c[i]] = 0; //初始石子堆花费显然为0
        }
        for(int len=1;len<=n;len++)
            for(int i=1;i+len-1<=n;i++) {
                int j=i+len-1;
                for(int col=0;col<3;col++) {
                    int min = inf;
                    for(int k=i;k<j;k++) {
                        if(dp[i][k][col]!=inf && dp[k+1][j][col]!=inf) {
                            min = Math.min(min, dp[i][k][col] + dp[k+1][j][col]);
                        }
                    }
                    if(min==inf) continue;
                    num[i][j]=1;
                    dp[i][j][(col+1)%3] = Math.min(dp[i][j][(col+1)%3], min+sum[j]-sum[i-1]);
                    cost[i][j] = Math.min(dp[i][j][0], Math.min(dp[i][j][1], dp[i][j][2]));
                }
            }
        for(int k=1;k<=n;k++) 
            for(int i=1;i<=k;i++)
                for(int j=k+1;j<=n;j++) {
                    if(num[i][j] > num[i][k] + num[k+1][j]) {
                        num[i][j] = num[i][k] + num[k+1][j];
                        cost[i][j] = cost[i][k]+cost[k+1][j];
                    }
                    else if(num[i][j] == num[i][k] + num[k+1][j]) {
                        cost[i][j] = Math.min(cost[i][j], cost[i][k]+cost[k+1][j]);
                    }
                }
        pw.println(num[1][n]+" "+cost[1][n]);
    }
}

```

0.0分

8 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

Studying

这个代码应该有问题吧
带入下面数据
6
1 3 5 7 9 11
0 1 2 0 1 2
输出 6 0，这怎么可能是对的啊

2023-08-31 12:05:46

Alan

测试点怎么全部RuntimeError了

2023-06-04 10:23:06

迷你滨

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

指针做法

Lucky Word （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蓝桥杯2023年第十四届省赛真题-合并石子（区间dp）

评论区

精彩推荐

母牛的故事（C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

printf基础练习2 （有点不明白）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

母牛的故事（C语言代码）

Tom数（C语言代码）

整除问题（C语言代码）

迷你滨

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

指针做法

Lucky Word （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蓝桥杯2023年第十四届省赛真题-合并石子（区间dp）

评论区

精彩推荐

母牛的故事 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

printf基础练习2 （有点不明白）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

母牛的故事 （C语言代码）

Tom数 （C语言代码）

整除问题 （C语言代码）

　　评论区

母牛的故事（C语言代码）

母牛的故事（C语言代码）

Tom数（C语言代码）

整除问题（C语言代码）