洛谷上的数据比较水，n<=100，所以普通的O(n^3)也能过掉
但是hdu上的数据就比较恶心给力，所以普通的O(n^3)就过不掉了
于是自行百度了一下，找到了平行四边形优化
但是
我还是看不懂
只好把它的适用范围讲一下
直接粘贴好了
四边形不等式优化动态规划原理:
1.当决策代价函数w[i][j]满足w[i][j]+w[i’][j’]<=w[i'][j]+w[i][j’](i<=i’<=j<=j’)时,称w满足四边形不等式.当函数w[i][j]满足w[i’][j]<=w[i][j’] (i<=i’<=j<=j’)时,称w关于区间包含关系单调.
2.如果状态转移方程m为
且决策代价w满足四边形不等式的单调函数(可以推导出m亦为满足四边形不等式的单调函数),则可利用四边形不等式推出最优决策s的单调函数性,从而减少每个状态的状态数,将算法的时间复杂度由原来的O(n^3)降低为O(n^2).方法是通过记录子区间的最优决策来减少当前的决策量.令:
s[i][j]=max{k | m[i][j] = m[i][k-1] + m[k][j] + w[i][j]}
然后就看不懂了
证明过程更看不懂了
先贴上洛谷 1880的代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=200; int dp1[N][N],dp2[N][N],sum[N],d[N]; int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&d[i]),d[i+n]=d[i]; for(int i=1;i<=2*n;i++) { sum[i]=sum[i-1]+d[i]; dp2[i][i]=0; dp1[i][i]=0; } for(int len=2;len<=n;len++) { for(int i=1;i<=2*n-len+1;i++) { int j=i+len-1; dp2[i][j]=999999999; for(int k=i;k<j;k++) { dp1[i][j]=max(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]); dp2[i][j]=min(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]); } } } int ans1=0,ans2=999999999; for(int i=1;i<=n;i++) { ans1=max(dp1[i][i+n-1],ans1); ans2=min(dp2[i][i+n-1],ans2); } printf("%d %d ",ans2,ans1); return 0; }
接下来是平行四边形优化
hdu 3506
1 #include <cstdio>//看不懂的平行四边形优化 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 typedef long long ll; 6 const int N=2005; 7 ll dp1[N][N],dp2[N][N],sum[N],d[N],s[N][N]; 8 ll n; 9 int main() 10 { 11 while(scanf("%lld",&n)!=EOF) 12 { 13 memset(dp2,0,sizeof(dp2)); 14 memset(d,0,sizeof(d)); 15 memset(s,0,sizeof(s)); 16 for(ll i=1;i<=n;i++) 17 scanf("%lld",&d[i]),d[i+n]=d[i]; 18 for(ll i=1;i<=2*n;i++) 19 { 20 sum[i]=sum[i-1]+d[i]; 21 dp2[i][i]=0; 22 s[i][i]=i; 23 } 24 for(ll len=2;len<=n;len++) 25 { 26 for(ll i=1;i<=2*n-len+1;i++) 27 { 28 ll j=i+len-1; 29 dp2[i][j]=99999999999; 30 for(ll k=s[i][j-1];k<=s[i+1][j];k++) 31 { 32 ll t=dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]; 33 if(dp2[i][j]>t) 34 { 35 s[i][j]=k; 36 dp2[i][j]=t; 37 } 38 } 39 } 40 } 41 ll ans2=999999999; 42 for(ll i=1;i<=n;i++) 43 { 44 ans2=min(dp2[i][i+n-1],ans2); 45 } 46 printf("%lld ",ans2); 47 } 48 49 return 0; 50 }
这两题就是很裸的区间dp
稍微看一下就懂了
我还是太垃圾了