DPまとめコンテスト N - Slimes

概要

項の数列が与えられる。この数列の隣接2項を足し合わせて1つの項にまとめることを繰り返し、最終的に1つの項からなる数列に変換することを考える。
項と項をまとめる際、のコストがかかるとする。最終的に1つの項にするための必要なコストの最小値を求めよ。

制約

方針

dp[i][j]をからまでの項をまとめるときの最小コストとする。
dp[i][j]はなるを用いて、「からまで、からまでを先にまとめ、その後その2つをまとめる」という操作に分解し、遷移させる。
「その後その2つをまとめる」ときにかかるコストはであるが、これは累積和で前もって計算させておく。

解答

Submission #4066057 - Educational DP Contest / DP まとめコンテスト

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	ll INF = 1e15;
	ll a[N+2];
	a[0] = INF;
	rep(i, N) cin >> a[i+1];
	a[N+1] = INF;
 
	ll s[N+2	];
	s[0] = 0;
	rep(i, N) s[i+1] = s[i] + a[i+1];
	s[N+1] = s[N];
 
	ll dp[N+1][N+1];
	rep(i, N+1) rep(j, N+1) dp[i][j] = ((i == j) ? 0 : INF);
 
	for(int w = 1; w <= N; w++){
		for(int l = 1; l+w <= N; l++){
			for(int k = 0; k <= w-1; k++){
				int r = l+w;
				dp[l][r] = min(dp[l][r], dp[l][l+k] + dp[l+k+1][r] + s[r] - s[l-1]);
			}
		}
	}
 
	cout << dp[1][N] << endl;
}