Lib/区間DP

ある区間[l,r)に対する関数が、それが内包する区間の組み合わせで高速に求まる場合、区間を状態に持ってDPが可能(N^2 * 遷移)

典型的には N ~= 500 (3乗)

[l,i)+[i,r) (l<i<r)のmin

[l,r-1)に1要素追加が高速　とか (N^2)

code:cpp

signed main() {

ll n;

cin >> n;

vector<ll> s(n);

vector<vector<ll>> dp(n+1,vector<ll>(n+1,inf));

rep1(range,n+1){

for(ll l=0;l+range<=n;l++){

ll r = l+range;

// print(l,r);

if(range == 1){

}else{

for(ll mid=l;mid<=r;mid++){

// print(l,mid,r);

}

}

}

}

}