区间 DP
2026-06-19 20:46:45
发布于：上海
14阅读
0回复
0点赞
万能开头@78鼠鼠 @156****6690@仰天长啸你爹驾到@AC酱
合并石子（随便合并）
#include<bits/stdc++.h>
using namespace std;
const long long MOF=0x3f3f3f3f3f3f3f3f;
int main(){
long long n,a[114],b[114];
long long dp[114][114];
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
b[i]=b[i-1]+a[i];
}
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;i++){
dp[i][i]=0;
}
for(int len=2;len<=n;len++){
for(int l=1;l<=n;l++){
int r=l+len-1;
if(r>n)break;
for(int k=l;k<=r-1;k++)dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+b[r]-b[l-1]);
}
}cout<<dp[1][n];
return 0;
}
旁边的
#include<bits/stdc++.h>
using namespace std;
const long long MOF=0x3f3f3f3f3f3f3f3f;
int main(){
long long n,a[1145],b[1145];
long long dp[214][214];
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;i<=n*2;i++){
b[i]=b[i-1]+a[i];
}
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n*2;i++){
dp[i][i]=0;
}
for(int len=2;len<=n;len++){
for(int l=1;l<=n;l++){
int r=l+len-1;
if(r>n*2)break;
for(int k=l;k<=r-1;k++)dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+b[r]-b[l-1]);
}
}long long ans=MOF;
for(int i=1;i<=n;i++){
ans=min(ans,dp[i][i+n-1]);
}cout<<ans;
return 0;
}
有帮助，赞一个