yukicoder : No.506 限られたジャパリまん

これも途中で星が増えたタイプかな。
https://yukicoder.me/problems/no/506

問題

(0,0)から隣接する格子点を辿り(W,H)に到達する最短経路を考える。
途中K個の格子点は通過できないが、K個中P個の頂点を選択し、通過可能にできる。

経路を最大化する選択と、その経路数を求めよ。

解法

Kが小さいので選択を全通り試し、それぞれDPで経路数を求めればよい。

int H,W,K,P;
int ID[40][40];
string S[50];
ll pat[50][50];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K>>P;
	MINUS(ID);
	FOR(i,K) {
		cin>>x>>y>>S[i];
		ID[x][y]=i;
	}
	
	ll ma=0;
	int tmask=-1;
	
	for(int mask=0;mask<1<<K;mask++) {
		if(__builtin_popcount(mask)>P) continue;
		ZERO(pat);
		pat[0][0]=1;
		FOR(x,H+1) FOR(y,W+1) if(x||y) {
			if(ID[x][y]>=0 && (mask&(1<<ID[x][y]))==0) continue;
			if(x) pat[x][y]+=pat[x-1][y];
			if(y) pat[x][y]+=pat[x][y-1];
		}
		if(pat[H][W]>ma) {
			ma=pat[H][W];
			tmask=mask;
		}
	}
	
	if(tmask==-1) return _P("0\n");
	cout<<ma%mo<<endl;
	FOR(i,K) if(tmask&(1<<i)) cout<<S[i]<<endl;
	
}

まとめ

やることは明確なので、★2.5位でもいい気がするな。