20分·第一个点(石子合并)
查看原帖
20分·第一个点(石子合并)
267517
Mikemao666楼主2020/7/22 11:46

要来一个标程,发现最小值错了。。。

#include <bits/stdc++.h>
using namespace std;
int n,ans1=-1,ans2=0x3f3f3f;
int a[101],sum[101];
int dp[203][203];
int dp1[203][203];
int main() {
	int n;
	memset(dp,0x3f3f3f,sizeof(dp));
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		scanf("%d",&a[i]);
		a[n+i]=a[i];
	}
	for(int i=1; i<=2*n; ++i) {
		sum[i]=sum[i-1]+a[i];
		dp[i][i]=0;
	}
	for(int len=1; len<=n; ++len) {
		for(int i=1; i<=2*n-len+1; i++) {
			int k=i+len-1;
			for(int j=i; j<k; ++j) {
				dp[i][k]=min(dp[i][k],dp[i][j]+dp[j+1][k]+sum[k]-sum[i-1]);
				dp1[i][k]=max(dp1[i][k],dp1[i][j]+dp1[j+1][k]+sum[k]-sum[i-1]);
			}
		}
		ans1=max(ans1,dp1[len][len+n-1]);
		ans2=min(ans2,dp[len][len+n-1]);
	}
	cout<<ans2<<endl<<ans1;
	return 0;
}
2020/7/22 11:46
加载中...