2018.10.27 loj#2292. 「THUSC 2016」成绩单(区间dp)
传送门
g[i][j][k][l]g[i][j][k][l]g[i][j][k][l]表示将区间l,rl,rl,r变成最小值等于kkk,最大值等于lll时的花费的最优值。
f[i][j]f[i][j]f[i][j]表示取掉区间l,rl,rl,r的最优值。
考虑ggg数组的转移。
g[i][j+1][min(k,w[j+1])][max(l,w[i+1])]=min(g[i][j+1][min(k,w[j+1])][max(l,w[i+1])],g[i][j][k][l])g[i][j+1][min(k,w[j+1])][max(l,w[i+1])]=min(g[i][j+1][min(k,w[j+1])][max(l,w[i+1])],g[i][j][k][l])g[i][j+1][min(k,w[j+1])][max(l,w[i+1])]=min(g[i][j+1][min(k,w[j+1])][max(l,w[i+1])],g[i][j][k][l])
g[i][t][k][l]=min(g[i][t][k][l],g[i][j]][k][l]+f[i+1][t])g[i][t][k][l]=min(g[i][t][k][l],g[i][j]][k][l]+f[i+1][t])g[i][t][k][l]=min(g[i][t][k][l],g[i][j]][k][l]+f[i+1][t])
然后再用ggg数组更新fff数组。
f[l][r]=min(f[l][r],g[l][r][k][l])f[l][r]=min(f[l][r],g[l][r][k][l])f[l][r]=min(f[l][r],g[l][r][k][l])
这样维护就行了。
注意dpdpdp之前离散化一下。
代码:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=55;
int n,a,b,f[N][N],g[N][N][N],w[N],x[N],tot=0;
int main(){
n=read(),a=read(),b=read();
for(int i=1;i<=n;++i)w[i]=x[i]=read();
sort(x+1,x+n+1),tot=unique(x+1,x+n+1)-x-1;
for(int i=1;i<=n;++i)w[i]=lower_bound(x+1,x+tot+1,w[i])-x;
for(int i=1;i<=n;++i)f[i][i]=a;
for(int len=2;len<=n;++len)for(int l=1,r=len;r<=n;++l,++r){
for(int i=l;i<=r;++i)for(int j=tot;j;--j)for(int k=tot;k>=j;--k)g[i][j][k]=0x3f3f3f3f;
g[l][w[l]][w[l]]=0;
for(int i=l;i<r;++i)for(int j=tot;j;--j)for(int k=tot;k>=j;--k){
if(g[i][j][k]==0x3f3f3f3f)continue;
int&tmp=g[i+1][min(j,w[i+1])][max(k,w[i+1])];
tmp=min(tmp,g[i][j][k]);
for(int t=i+1;t<=r;++t)g[t][j][k]=min(g[t][j][k],g[i][j][k]+f[i+1][t]);
}
f[l][r]=0x3f3f3f3f;
for(int i=tot;i;--i)for(int j=tot;j>=i;--j)f[l][r]=min(f[l][r],g[r][i][j]+a+b*(x[i]-x[j])*(x[i]-x[j]));
}
cout<<f[1][n];
return 0;
}
最新文章
- Java读写文件的几种方法
- Asp.Net MVC Filter 实现方式和作用范围控制
- HBase + Kerberos 配置示例(二)
- sass的安装与基础
- [转]Android在eclipse中的快捷键
- Linux下tar bz gz等压缩包的压缩和解压
- Oracle数据泵(上)
- maven中运行java程序
- python tkinter entry
- Nginx简单手册
- nw.js---开发一个百度浏览器
- [leetcode]70. Climbing Stairs爬楼梯
- jps报process information unavailable的解决办法
- 七台机器部署Hadoop2.6.5高可用集群
- effective c++ 笔记 (49-52)
- XML和JSON优缺点
- Fix SCRIPT5009: “RegisterSod” undefined error
- VS 常见快捷键有哪些
- IOS7 UI设计的十大准则
- 详细MATLAB 中BP神经网络算法的实现
热门文章
- 22. Generate Parentheses (backTracking)
- mybatis BigDecimal Double Long 的坑爹事
- AtCoder Regular Contest 096 D - Static Sushi(线性dp)
- [剑指Offer]23-链表中环的入口节点
- Netty---入门程序,搭建Websocket 服务器
- day 13 模块
- Flex 布局排版总结
- linux命令学习之:wc
- subprocess.Popen在win10下会有异常
- SSH Secure File Transfer Client 无法登陆