CF 1312 E Array Shrinking(区間dpテンプレート)

タイトルリンク(洛谷)CodeForces
これは区間dpの板題です
に言及
1つの配列が与えられ、2つの隣接する数に対して、それらが等しい場合、それらを1つの数にマージすることができ、その値は原数+1+1であり、元の配列のマージ後の最小長を求めることができる.
構想
まずこの説明を見てみましょう区間dp区間d pのテンプレート:d p[i][j]=min⁡(d p[i]+d p[k+1][j]+w[i])(w[i]テーマによって変化)区間dpのテンプレート:dp[i][j]=min(dp[i][k]+dp[k+1][j]+w[i])(w[i]テーマによって変化)区間dpのテンプレート:dp[i][j]=min(dp[i][k]+dp[k]+j]+w[i])d p[i][j]dp[i][j]dp[i][j]を区間[i,j][i,j][i,j]にマージできる最小長とすることを考慮し、w[i][j]w[i][j]w[i][j]が区間[i,j][i,j][i,j][i,j]で統合できる和を簡単に得ることができるこのような式のd d p[i][j]=min⁡(d p[i][j],d p[i][k]+d p[k+1][j])dp[i][j]=min(dp[i][j],dp[i][j]+dp[k]+dp[k]+dp[k+1][j])dp[i][j]=min(dp[i][j]=min(dp[i][j],dp[k]+dp[k]+dp[k]+dp[k j])そしてどのようにこのテーマの合併を保証することができますか?i,j,k i,j,k,j,kを列挙するたびにこのように更新することを考えることができます.

if (dp[i][k] == 1 && dp[k + 1][j] == 1 && w[i][k] == w[k + 1][j])
	dp[i][j] = 1, w[i][j] = w[i][k] + 1;

最後にd p[1][n]dp[1][n]dp[1][n]を直接出力すればよい
コード#コード#
具体的な実装については、コードを参照してください.

const int N = 505, INF = 0x3f3f3f3f;
int n, dp[N][N], w[N][N];
// dp[i][j]:[i, j]       
// w[i][j]:[i, j]      
int main()
{
	memset(dp, 0x3f, sizeof dp);
	rd(n);
	for (int i = 1; i <= n; i++)
		rd(w[i][i]), dp[i][i] = 1;
	for (int len = 2; len <= n; len++)
		for (int i = 1; i <= n - len + 1; i++)
		{
			int j = len + i - 1;
			for (int k = i ; k < j; k++)
			{
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
				if (dp[k + 1][j] == 1 && dp[i][k] == 1 && w[i][k] == w[k + 1][j]) //          1，     ，    
					dp[i][j] = 1, w[i][j] = w[i][k] + 1;
			}
		}
	pt(dp[1][n]);
	return 0;
}

ありがとう