AcWing 282. (虽然没有所有的数据)我是跑的最快的!
原题链接
简单
作者:
eMAY
,
2019-11-02 20:31:08
,
所有人可见
,
阅读 816
这里有两种算法
1。区间DP
#include<bits/stdc++.h>
using namespace std;
int n;
int f[309][309];
int a[309],sum[309];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)f[i][i]=0;
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int k=l;k<r;k++){
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
}
}
}
printf("%d",f[1][n]);
return 0;
}
2。这种算法可以做更大范围的数据,在这里大材小用了
而且跑的飞快,他的名字叫做GarsiaWachs算法,感兴趣的同学可以了解下
#include<bits/stdc++.h>
using namespace std;
vector<int> l;
int n,ans;
inline int read(){
int x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int merge(){
int k=l.size()-1-1;
int size=l.size()-2;
for(int i=0;i<size;i++){
if(l[i]<=l[i+2]){
k=i;
break;
}
}
int tmp=l[k]+l[k+1];
l.erase(l.begin()+k);
l.erase(l.begin()+k);
int in=-1;
for(int i=k-1;i>=0;--i){
if(l[i]>tmp){
in=i;
break;
}
}
l.insert(l.begin()+in+1,tmp);
return tmp;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
l.push_back(read());
}
for(int i=0;i<n-1;i++){
ans+=merge();
}
printf("%d",ans);
return 0;
}