Codeforces 18 D. Seller Bob

問題

Bobはn日間メモリの商売をする。
n日目の行動は以下の形式で与えられる。

• win x 2^xMBのメモリを勝ち取る。このメモリは、自分が持つか友人にタダであげるかする
• sell x 2^xMBのメモリを欲しがる客が来る

Bobはメモリを同時に一つしか持てず、客がちょうど欲しがるサイズのメモリしか売ることが出来ない。
2^xMBのメモリを売ると、2^xドルの利益が出る。

Bobの得られる最大の利益を求めよ。

制約条件

n≦5000
x≦2000

方針

動的計画法による。
dp[i]をi日目まででBobが出せる最大の利益とする。

i日目に2^xMBのメモリを求める客が来るとすると、
2^xMBのメモリを最後に入手した日をpos[x]日目として、
dp[i]=max(dp[i-1],dp[pos[x] ]+2^x)と書ける。
この漸化式に従い、テーブルを更新していけばO(n)で答えが求まる。
答えは大きいのでBigIntegerを使う必要がある。

ソースコード

public class CF18D {
	public static void main(String args[]) {
		new CF18D().run();
	}
	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] pos = new int[2001];
		for(int i = 0; i < 2001; i++) pos[i] = -1;
		
		BigInteger[] dp = new BigInteger[n+1];
		dp[0] = BigInteger.ZERO;
		
		for(int i = 1; i <= n; i++){
			String s = sc.next();
			int x;
			x = sc.nextInt();
			dp[i] = dp[i-1];
			if(s.compareTo("win") == 0)
				pos[x] = i;
			else{
				if(pos[x] >= 0 &&
dp[i].compareTo(dp[pos[x]].add(BigInteger.ONE.shiftLeft(x))) < 0)
			dp[i] = dp[pos[x]].add(BigInteger.ONE.shiftLeft(x));
			}
		}
		System.out.println(dp[n]);
	}
}