シール枚

12407 ワード
DP boj テキストリンク
質問リンク

1.トラブルシューティング


問題に明確な条件を以下のように整理する.
  • 題では,現在座標(a,b)のシールを外すと,左(a,b−1),右(a,b+1),下(a+1,b),上(a−1,b)を取り除くことができない.
  • シールを外さなくてもいいです.
    • n<=10000を考慮するとbrute forceはタイムアウトします.そのため、私たちは大きな問題を一部の問題に分けて考えるべきだ.

    1-1. 部分的な問題に分ける


    大きな問題は「何枚かのシールを引き裂いても最大点数がもらえる」ということです.これを「現在の座標(x,y)に格納されている最大スコア」という一部の問題に分けます.
    したがって,座標(x,y)上の最大スコアが注釈の対象となる.

    1-2. 開けますか?もういいよ。


    問題では2つの行動をとることができます.
  • 現在座標(x,y)のシールを取り外します.
    隣接する
  • のシールは取り外すことができず、上下に取り外します.したがってmod演算を用いる.
  • は取り外さず、次のコーナーに進みます.

    • 2.ソースコード

    //스티커
import java.io.*;
import java.util.*;

public class Main {
	static int [][]cache, array;
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int i =0 ; i < tc ; i++) {
			int n = Integer.parseInt(br.readLine());
			
			StringTokenizer st =null;
			array = new int[2][n];
			for(int j =0 ; j < 2 ; j++) {
				st= new StringTokenizer(br.readLine());
				
				for(int k =0 ; k < n ; k++) {
					array[j][k] = Integer.parseInt(st.nextToken());
				}
			}
			
			cache = new int[2][n];
			
			for(int [] c : cache)
				Arrays.fill(c, -1);
			
			System.out.println(Math.max(dp(0,0), dp(1,0)));
		}
	}
	
	private static int dp(int x, int y) {
		if(y == array[x].length)
			return 0;
		
		if(cache[x][y] != -1)
			return cache[x][y];
		
		int ret =0;
		
		//현재 스티커를 떄는 경우
		ret = dp((x+1)%2, y+1) + array[x][y];
		
		//안 때는 경우
		ret = Math.max(dp(x,y+1),ret);
		
		return cache[x][y] = ret;
	}
}
    帆ソフトの異なる位置で異なる位置コントロールを取得し、コントロールの一般的な方法
    AVA-4:制御文