相邻石子合并问题
代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i = a; i <= n; i++)
const int N = 330;
int sum[N];
int a[N];
int f[N][N];//从i到j合并石子所付出的最小代价
int main(){
int n;cin>>n;
rep(i,1,n){
cin >> a[i];
sum[i] += sum[i - 1] + a[i];
}
rep(len,2,n){//长度
rep(i,1,n- len + 1){//左端点
int l = i, r = i + len - 1;//右端点
f[l][r] = 1e9;//初始化为最大值
rep(k,l,r -1){
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);//动态规划
}
}
}
cout << f[1][n] << endl;
return 0;
}
环形石子合并问题
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i = (a); i <= (n); i++)
const int N = 500;
int f[N][N],v[N][N];
int a[N],sum[N];
int main(){
int n; cin >> n;
rep(i,1,n){
cin >> a[i];
a[i + n] = a[i];
}
rep(i,1,2 * n){
sum[i] = sum[i - 1] + a[i];
}
rep(len,2,n){
rep(l,1,2 * n - len + 1){
int r = l + len - 1;
f[l][r] = 1e9;
rep(k,l,r - 1){
f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);
v[l][r] = max(v[l][r],v[l][k] + v[k + 1][r] + sum[r] - sum[l - 1]);
}
}
}
int ans1 = 1e9, ans2 = 0;
for(int i = 1; i <= n; i++){
ans1 = min(ans1,f[i][i + n - 1]);
ans2 = max(ans2,v[i][i + n - 1]);
}
cout << ans1 << endl;
cout << ans2;
return 0;
}