十四届蓝桥杯JAVA-b组-合并石子

 点我写题

思路：区间dp和缝合dp板子题，先用个dp[i][j][k]表示考虑区间[i,j]合并成颜色k的最小代价，然后用min[i][j]存一下[i,j]区间合并的最小代价，即min(dp[i][j][0-2])，has[i][j]表示区间[i,j]是否能合并，上面提到的部分都能用区间dp处理出来，接下来就是求具体答案的dp,缝合板子，用个ds[i]表示前i个数最少能分成几段，转移很显然，枚举前面的j，然后判断[i,j]这一段是不是能合并，然后ds[i]=min(ds[i],ds[j-1]+1),这样答案的前一部分就求好了，然后考虑ak[i][k],即前i个数分成k段的最小代价，也就是答案的第二部分，也是缝合板子题，先判断前面的j是否能成为一段然后取min转移即可，具体看代码

内心ps:蓝桥云课的代码区挺难用的，哎，这题挺板的思路很明显，写了20min就过了。。

import java.io.*;
import java.util.*;
public class Main{public static void main(String args[]){Scanner s=new Scanner(System.in);int n=s.nextInt();long dp[][][]=new long [n+10][n+10][3];long min[][]=new long [n+10][n+10];int dj[]=new int [n+10],col[]=new int [n+10];int sum[]=new int [n+10];for(int i=1;i<=n;i++){dj[i]=s.nextInt();sum[i]=sum[i-1]+dj[i];}for(int i=1;i<=n;i++) col[i]=s.nextInt();for(int i=0;i<n+10;i++){Arrays.fill(min[i],(long)1e18);for(int j=0;j<n+10;j++){Arrays.fill(dp[i][j],(long)1e18);}}for(int i=1;i<=n;i++){dp[i][i][col[i]]=0;min[i][i]=0;}boolean has[][]=new boolean [n+10][n+10];for(int i=1;i<=n;i++) has[i][i]=true;for(int len=2;len<=n;len++){for(int i=1;i+len-1<=n;i++){int j=i+len-1;for(int k=i;k<j;k++){for(int u=0;u<3;u++){int ne=(u+1)%3;dp[i][j][ne]=Math.min(dp[i][j][ne],dp[i][k][u]+dp[k+1][j][u]+sum[j]-sum[i-1]);if(dp[i][j][ne]<(long)1e18){//   System.out.println(i+" "+j+" "+ne);has[i][j]=true;min[i][j]=Math.min(min[i][j],dp[i][j][ne]);}}}}}int ds[]=new int [n+10];//   ds[1]=1;for(int i=1;i<=n;i++){ds[i]=i;for(int j=1;j<=i;j++){if(has[j][i]){//    System.out.println(j+" "+i);ds[i]=Math.min(ds[i],ds[j-1]+1);//  break;}}}long ak[][]=new long [n+10][ds[n]+10];for(int i=0;i<n+10;i++) Arrays.fill(ak[i],(long)1e18);ak[0][0]=0;//考虑前i个数分成p段的最小代价// System.out.println("fdsaf");for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){if(has[j][i]==false) continue;for(int p=1;p<=Math.min(ds[n],i);p++){ak[i][p]=Math.min(ak[i][p],ak[j-1][p-1]+min[j][i]);}}}//  System.out.println(ds[n]);System.out.println(ds[n]+" "+ak[n][ds[n]]);}
}
// 1 2 2
// 4 5 0
// 3 5 1
// 3 5 1
// 2 5 2
// 2 5 2
// 2 5 2
// 0