1. 石子归并 https://vjudge.net/problem/51Nod-1021
非常朴素, 顺着推即可
w [ i ] [ j ] 表示把第 i 堆到第 j 堆的石子和到一起的最后一步的代价
- f [ i ] [ j ] = min{f [ i ] [ k ] + f [ k+1 ] [ j ] + w[ i ] [ j ] | i <= k <j , i <= j}
- for(int i=1;i<=n;++i)// 长度
- for(int j=1;j+i<=n+1;++j)// 起点
- {
- int e=j+i-1;
- for(int k=j;k<e;++k)// 分割点
- {
- dp1[j][e]=min(dp1[j][k]+dp1[k+1][e]+sum[e]-sum[j-1],dp1[j][e]);
- }
- }
2.[NOI1995] 石子合并 https://www.luogu.org/problemnew/show/P1880
在上面那个问题略微变动一下, 变成了环形, 可以将其暴力拆成链
- void read()
- {
- memset(dp1,0x3f,sizeof(dp1));
- red(n);
- for(int i=1;i<=n;++i)
- {
- red(a[i]);
- a[i+n]=a[i];
- }
- }
- void work()
- {
- for(int i=1;i<=2*n;++i)
- {
- sum[i]=sum[i-1]+a[i];
- dp1[i][i]=0;
- }
- for(int i=1;i<=n;++i)
- for(int j=1;j+i<2*n;++j)
- {
- int e=j+i-1;
- for(int k=j;k<e;++k)
- {
- dp1[j][e]=min(dp1[j][k]+dp1[k+1][e]+sum[e]-sum[j-1],dp1[j][e]);
- dp2[j][e]=max(dp2[j][k]+dp2[k+1][e]+sum[e]-sum[j-1],dp2[j][e]);
- }
- }
- minn=INF;
- for(int i=1;i<=n;++i)
- {
- minn=min(minn,dp1[i][i+n-1]);
- maxx=max(maxx,dp2[i][i+n-1]);
- }
- printf("%d\n%d",minn,maxx);
- }
3. 四边形优化
上面的朴素写法复杂度都是 O(n^3), 有没有更好的写法吗?
有, 利用数学里的四边形不等式
f[a][c]+f[b][d]<=f[b][c]+f[a][d]
交叉小于包含, 即交叉的两个区间, a 到 c 和 b 到 d 的值满足小于等于包含的两个区间 [bc 包含于 ad])
则说这个东西满足四边形不等式
简而言之, 就是该区间的最优分割点一定在前一个区间和后一个区间之间, 即:
- s [ i ] [ j - 1 ] <= s [ i ] [ j ] <= s [ i + 1 ] [ j ]
- for(int i=1;i<=n;++i)
- for(int j=1;j+i<2*n;++j)
- {
- int e=j+i-1;
- for(int k=r[j][e-1];k<=r[j+1][e];++k)
- {
- if(dp1[j][e]>dp1[j][k]+dp1[k+1][e]+sum[e]-sum[j-1])
- {
- dp1[j][e]=dp1[j][k]+dp1[k+1][e]+sum[e]-sum[j-1];
- r[j][e]=k;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3044303.html