题目链接
题目解法
咋神仙区间 \(dp\) 题永远想不到区间 \(dp\)???
首先把操作顺序反转
那么现在的问题就是:每次可以选出一个子序列放到序列末尾,使序列升序的最小代价
这个问题看着也是毫无头绪
我尝试去找些规律,当然也没找到
考虑精细刻画操作过程:最终的序列是升序的,最后一次操作是找到两个升序子序列 \([1,x]\) 和 \([x+1,n]\)(值域上),然后继续去划分 \([1,x]\),\([x+1,n]\) 到更小的值域范围
可能唯一能想到的入手点就是从这个过程出发,从而得到区间 \(dp\)
令 \(f_{i,l,r}\) 为操作了 \(i\) 次,把 \([l,r]\) 排好序的最小代价
转移不难得到为:
\(f_{i,l,r}\to f_{i+1,l,r}\)
\(f_{i,l,q}+f_{i,q+1,r}+c_{k-i+1}\times (r-q)\to f_{i+1,l,r}\)(注意操作是逆序的,所以乘的是 \(c_{k-i+1}\))
时间复杂度 \(O(n^3k)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=110;
int n,k,c[N],p[N],rv[N];
LL f[N][N][N];
int main(){
n=read(),k=read();
F(i,1,k) c[i]=read();
F(i,1,n) p[i]=read(),rv[p[i]]=i;
ms(f,0x3f);
F(i,1,n){
f[0][i][i]=0;
int la=rv[i];
F(j,i+1,n){
if(rv[j]<la) break;
f[0][i][j]=0,la=rv[j];
}
}
F(i,1,k)
F(len,1,n) F(l,1,n-len+1){
int r=l+len-1;
f[i][l][r]=f[i-1][l][r];
F(q,l,r-1) chkmin(f[i][l][r],f[i-1][l][q]+f[i-1][q+1][r]+1ll*c[k-i+1]*(r-q));
}
if(f[k][1][n]>1e18) puts("-1");
else printf("%lld\n",f[k][1][n]);
return 0;
}
标签:Insert,ch,int,题解,long,序列,Split,升序,define
From: https://www.cnblogs.com/Farmer-djx/p/18013036