石子合并问题

相邻石子合并问题

代码

#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;
}