原始写法
#include <iostream>
using namespace std;
const int N = 1001;
int a,b;
int x[N],y[N],z[N][N];
int main(){
cin >> a;
for (int i = 1; i <= a; i ++ ){
cin >> x[i];
x[i] += x[i - 1];
}
for (int i = 2; i <= a; i ++ ){
for (int j = 1; i + j - 1 <= a; j ++ ) {
int l = j;
int r = i + j - 1;
z[l][r] = 1e8;
for (int k = l; k <= r; k ++ ) {
z[l][r] = min(z[l][r],z[l][k] + z[k + 1][r] + x[r] - x[l - 1]);
}
}
}
cout << z[1][a];
}
自己写的方法
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#define ll long long
#define rep(i,a,n) for(ll i = a; i <= n; i ++)
#define per(i,a,n) for(ll i = n; i >= a; i --)
#define pb push_back
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define ld long double
const ll N = 2e3 + 10;
//ll op[N][N];
ll dp[N][N];
void solve(){
ll n;
std::cin >> n;
std::vector<ll> op(n + 1),cxk(n + 1);
rep(i,1,n){
std::cin >> op[i];
cxk[i] = cxk[i - 1] + op[i];
}
rep(i,1,n){
rep(j,1,n){
if(i == j) dp[i][j] = 0;
else dp[i][j] = 1e9 + 10;
}
}
per(i,1,n){//左端点
rep(j,i + 1,n){//右端点
rep(k,i,j){
dp[i][j] = std::min(dp[i][j],dp[i][k] + dp[k + 1][j] + cxk[j] - cxk[i - 1]);
}
}
}
std::cout << dp[1][n] << "\n";
return ;
}
int main(){
// int t;
// std::cin >> t;
// while(t --)
solve();
return 0;
}
扩展:环形石子合并
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#define ll long long
#define rep(i,a,n) for(ll i = a; i <= n; i ++)
#define per(i,a,n) for(ll i = n; i >= a; i --)
#define pb push_back
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define ld long double
const ll N = 230 + 10;
ll dp[N + 3][N + 3];
ll pd[N + 3][N + 3];
void solve(){
ll n;
std::cin >> n;
std::vector<ll> op(n * 3 + 1),cxk(n * 3 + 1);
rep(i,1,n){
std::cin >> op[i];
}
rep(i,1,n * 2){
if(i <= n) cxk[i] = cxk[i - 1] + op[i];
else cxk[i] = cxk[i - 1] + op[i - n];
}
rep(i,1,n * 2 + 1){
rep(j,1,n * 2 + 1){
if(i == j){
dp[i][j] = 0;
pd[i][j] = 0;
}
else {
dp[i][j] = 1e6 + 10;
pd[i][j] = -1e6 + 10;
}
}
}
rep(i,1,n){//个数端点
for(ll j = 1;i + j - 1 <= 2 * n; j ++){//左端点
rep(k,j,i + j - 2){
pd[j][i + j - 1] = std::max(pd[j][i + j - 1],pd[j][k] + pd[k + 1][i + j - 1] + cxk[i + j - 1] - cxk[j - 1]);
dp[j][i + j - 1] = std::min(dp[j][i + j - 1],dp[j][k] + dp[k + 1][i + j - 1] + cxk[i + j - 1] - cxk[j - 1]);
}
}
}
ll res = 1e6 + 10;
ll mm = -1e6 + 10;
rep(i,1,n){
res = std::min(res,dp[i][i + n - 1]);
mm = std::max(mm,pd[i][i + n - 1]);
}
std::cout << res << "\n";
std::cout << mm << "\n";
return ;
}
int main(){
// int t;
// std::cin >> t;
// while(t --)
solve();
return 0;
}