AtCoder ABC 224E - Integers on Grid 解題心得( 題目 )
心得:這次第一次寫這個網站(AtCoder)，先選了比較簡單的AtCoder Beginner Contest中的題目，其中題目有A~H八題，這次選了E(題目難度越後面越難，E比較貼近我目前的程度)
提醒:public class 要打Main!!
解題概念:DP
解題方法:這題我們可以定義dp[axis][i]=j代表如果在該軸的第i行可得到的最佳值，所以如果我們以x軸的axis為0，y為1，則在(A,B)點可得為Math.max(dp[0][A],dp[1][B])
而我們的DP需要轉移，就是我們從比較大的值開始往下看，在拿了值後同時轉移(將那一個的x,y方向的DP加上1)，不過注意這題有可能有兩個以上網格的值一樣，所以在轉移時先透過兩個方向的HashSet先記著，等跑完所有同樣數字的再轉移。
Java參考程式碼(有更好意見可留言於下方，謝謝!)
import java.io.*;
import java.util.*;
public class Main {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static int r,ret;
public static int[][] dp=new int[2][200005];
public static void main(String[] args) throws Exception {
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
final int h=readint();
final int w=readint();
final int n=readint();
Grid[] g=new Grid[n];
for(int i=0;i<n;i++) {
g[i]=new Grid(readint(),readint(),readint(),i);
}
Arrays.sort(g,new Comparator<Grid>() {
//大小排序(大->小)
public int compare(Grid ft,Grid sd) {
if(ft.a>sd.a) {
return -1;
}
if(ft.a==sd.a){
return 0;
}
return 1;
}
});
int ca=-1;//紀錄目前討論到的格子數字大小
Integer mg;//用來從map裡面取值(暫存)
HashMap<Integer,Integer> xp=new HashMap<>();//暫存x(當格子數字一樣)
HashMap<Integer,Integer> yp=new HashMap<>();//暫存y
for(int i=0;i<n;i++) {
if(ca!=g[i].a) {
//如果數字和前一個不同就轉移set
ca=g[i].a;
for(int j:xp.keySet()) {
dp[0][j]=Math.max(dp[0][j],xp.get(j));//轉移
}
for(int j:yp.keySet()) {
dp[1][j]=Math.max(dp[1][j],yp.get(j));//轉移
}
xp.clear();
yp.clear();
}
g[i].l=Math.max(dp[0][g[i].x],dp[1][g[i].y]);//求比較大的那個
mg=xp.get(g[i].x);
if(mg==null||mg<g[i].l+1) {
xp.put(g[i].x,g[i].l+1);//如果目前無或大於目前值
}
mg=yp.get(g[i].y);
if(mg==null||mg<g[i].l+1) {
yp.put(g[i].y,g[i].l+1);
}
}
Arrays.sort(g,new Comparator<Grid>() {
public int compare(Grid ft,Grid sd) {
if(ft.s>sd.s) {
return 1;
}
return -1;
}
//照輸出順序排序
});
for(int i=0;i<n;i++) {
bw.write(g[i].l+"\n");//輸出
}
bw.flush();
}
public static int readint() throws Exception {
//輸入
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class Grid{
int x,y,l,s,a;
//l 紀錄答案
//a 記錄格中數字
//s 紀錄輸出順序
Grid(int x,int y,int a,int s){
this.x=x;
this.y=y;
this.a=a;
this.s=s;
}
}
文章標籤
全站熱搜
