SRM 259 DIV1 Hard CardRemover

問題 Editorial

問題

3文字のアルファベット大文字が書かれたカードが何枚かある(cards)。
隣接する3つのカードの左右を選び、それらに共通する文字が2つ以上あるならば真ん中のカードを消すことができる。
カードを消せる最大枚数を求めよ

• 2 <= |cards| <= 50

解答

Editorialを参考にした。
区間DP。
[l, u]の区間は、任意のところで左右に分割して、その左右の真ん中の所は重複させて、そこを消すカードにする感じで

コメント

最大値を判定に使うのはいいなあ

コード

#include <string>
#include <vector>
#include <cstring>
#define mset(m,v) memset(m,v,sizeof(m))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
using namespace std;
bool ok[55][55];
int dp[55][55];
struct CardRemover {
	int rec(int l, int u) {
		if(dp[l][u] != -1) return dp[l][u];
		int r = 0;
		rer(i, l+1, u-1) {
			int s1 = rec(l, i), s2 = rec(i, u);
			if(s1 + s2 + 1 == u - l - 1 && ok[l][u]) r = max(r, s1 + s2 + 1);
			else r = max(r, s1 + s2);
		}
		return dp[l][u] = r;
	}
	int calculate(vector <string> cards) {
		int n = cards.size();
		rep(i, n) rep(j, n) {
			int x = 0; each(k, cards[i]) x += cards[j].find(*k) != -1;
			ok[i][j] = x >= 2;
		}
		mset(dp, -1);
		return rec(0, n-1);
	}
};