LeetCode Weekly Contest 126 : 1000. Minimum Cost to Merge Stones

難易度9だけどそれほど難しくはない？
https://leetcode.com/contest/weekly-contest-126/problems/minimum-cost-to-merge-stones/

問題

N要素の数列Aが与えられる。
長さKの部分列を選び、その区間をその総和で置き換える。
ただしその際のコストは、その総和に一致するものとする。

要素数が1になるまで上記手順を繰り返すとき、総コストの最小値を求めよ。

解法

下記を考え、f(0,N)を答えればよい。
f(L,R) := A[L..R)を単一要素にするまでかかるコストの最小値

これは以下のようになる。

• L+1=Rならf(L,R)=0
• (R-L-1)が(K-1)の倍数でないなら、条件を満たす解なし
• それ以外の場合、A[L..R)をK個の区間[L,M[0])、[M[0],M[1])...,[M[K-2],R)に分割したときのf(*,*)の総和に、A[L..R)の総和を足したもの

最後のケースはDPで求めても十分間に合う。

int memo[32][32];

class Solution {
public:
	int K;
	vector<int> S,sum;
	
	int dpdp(int L,int R) {
		if((R-L-1)%(K-1)) return -1;
		if(memo[L][R]>=0) return memo[L][R];
		if(R-L==1) return memo[L][R]=0;
		if(R-L==K) return memo[L][R]=sum[R]-sum[L];
		
		int mi[32][32];
		int x,y;
		FOR(x,31) FOR(y,31) mi[x][y]=1<<29;
		mi[0][L]=0;
		int i,j,k;
		FOR(i,K) {
			for(j=L;j<R;j++) if(mi[i][j]<1<<29) {
				for(k=j+1;k<=R;k++) {
					if(j==L && k==R) continue;
					int ret=dpdp(j,k);
					if(ret>=0) mi[i+1][k]=min(mi[i+1][k],mi[i][j]+ret);
				}
			}
		}
		
		return memo[L][R]=mi[K][R]+sum[R]-sum[L];
		
		
	}
	
    int mergeStones(vector<int>& stones, int K) {
		this->K=K;
		S=stones;
		sum.clear();
		sum.push_back(0);
		FORR(s,S) sum.push_back(sum.back()+s);
		MINUS(memo);
		return dpdp(0,S.size());
    }
};

まとめ

またわけのわからん問題番号のつけ方する…。