阿祁的部落格

ZeroJudge g113-太陽番茄 解題心得( 題目 )

解題概念:DP

解題方法:首先為了方便說明，定義由小到大方向為:左->右、前->後、上->下，例如(1,1,1)在(2,2,2)的左、上、前方。其實這題可以改求每一格能放的極限大小，然後再全部加總就是答案，我們定義dp[x][y][z]=m，代表最多可以放下一個座標範圍為(x-m+1,y-m+1,z-m+1)~(x,y,z)，大小m的正方體(例如如果題目以1,1,1為起點，完全沒有障礙則dp[1][1][1]=1、dp[3][3][3]=3、dp[5][4][3]=3)，另外決定這格可以放多大正方體的條件是在他左一格、上一格、前一格、左上、前上、左前、左前上總共七格中的dp最小值+1(我們從那七格可以知道這格放得下多大)，不過如果這格有障礙就是0)，轉移式為:dp[x][y][z]=min(dp[x-1][y][z],dp[x][y-1][z],dp[x][y][z-1],dp[x-1][y-1][z],dp[x][y-1][z-1],dp[x-1][y][z-1],dp[x-1][y-1][z-1])+1

Java參考程式碼(有更好意見可留言於下方，謝謝!)

//Author:En Chi Tsung(欉恩祁)

//Date:2021/10/23

import java.io.*;

public class zjg113 {

   public static int ret,r;
 
   public static long retl;
 
   public static int[][][] dp=new int[305][305][305];
 
   public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 
   public static void main(String[] args) throws Exception {
 
       final int a=rint();
 
       final int b=rint();
 
       final int c=rint();
 
       int min;
 
       long rt=0;
 
       for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)for(int k=1;k<=c;k++)dp[i][j][k]=1;//初始化
 
       final int t=rint();
 
       for(int i=0;i<t;i++) {
 
           dp[rint()][rint()][rint()]=0;//沒有的格子
 
       }
 
       for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)for(int k=1;k<=c;k++) {
 
           if(dp[i][j][k]!=0) {
 
               min=dp[i-1][j][k];//dp轉移(下面就是一串比大小)
 
               min=Math.min(dp[i][j-1][k], min);
 
               min=Math.min(dp[i][j][k-1], min);
 
               min=Math.min(dp[i-1][j-1][k], min);
 
               min=Math.min(dp[i][j-1][k-1], min);
 
               min=Math.min(dp[i-1][j][k-1], min);
 
               min=Math.min(dp[i-1][j-1][k-1], min);
 
               dp[i][j][k]=min+1;
 
               rt+=dp[i][j][k];//加總和
 
           }
 
       }
 
       System.out.println(rt);
 
   }
 
   
 
   public static int rint() throws Exception {
 
       //輸入
 
       ret=0;

       r=br.read();
 
       while(r>47&&r<58) {
 
           ret*=10;
 
           ret+=(r&15);
 
           r=br.read();
 
       }
 
       return ret;
 
   }

}