十四届蓝桥杯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