CCF 压缩编码（石子合并问题）

#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<stack> #include<set> using namespace std; typedef long long ll; const int maxn=300010; int n,m; int a[1010]; int dp[1010][1010]; int sum[1010]; int main(){ cin>>n; for(int i=1;i<=n;++i){ cin>>a[i]; sum[i]=sum[i-1]+a[i]; } if(n==1){ cout<<a[1]<<endl; return 0; } if(n==2){ cout<<a[1]+a[2]<<endl; return 0; } for(int i=1;i<n;++i){ dp[i][i+1]=a[i]+a[i+1]; } for(int len=3;len<=n;++len){ for(int i=1;i+len-1<=n;++i){ int j=i+len-1; dp[i][j]=0xfffffff; for(int k=i;k<=j;++k){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); } } } cout<<dp[1][n]<<endl; return 0; }

四边形不等式优化;

#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<stack> #include<set> using namespace std; typedef long long ll; const int maxn=1010; const int inf=0xfffffff; int n; int a[maxn]; int dp[maxn][maxn]; int sum[maxn]; int p[maxn][maxn]; int main(){ int i,j,k; while(~scanf("%d",&n)){ for(i=1;i<=n;++i){ scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; p[i][i]=i; dp[i][i]=0; } if(n==1){ printf("%d\n",a[1]); continue; } if(n==2){ printf("%d\n",a[1]+a[2]); continue; } int len; for(len=2;len<=n;++len){ for(i=1;i+len-1<=n;++i){ j=i+len-1; dp[i][j]=inf; for(k=p[i][j-1];k<=p[i+1][j];++k){ int s=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]; if(s<dp[i][j]){ dp[i][j]=s; p[i][j]=k; } } } } printf("%d\n",dp[1][n]); sum[0]=0; } return 0; }