1 条题解
-
1
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int sum=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ sum=sum*10+(c^48); c=getchar(); } return sum; } int const maxn=75; struct node{ int num, quan, pin; //数据值 权值 访问频度 }a[maxn]; inline bool cmp(node x,node y){ return x.num<y.num; } int n,K,b[maxn],sum[maxn],f[maxn][maxn][maxn]; signed main(){ n=read(),K=read(); for(int i=1;i<=n;i++) a[i].num=read(); for(int i=1;i<=n;i++) b[i]=a[i].quan=read(); for(int i=1;i<=n;i++) a[i].pin=read(); sort(a+1,a+n+1,cmp);//按照数据值从小到大排序,得到中序遍历 sort(b+1,b+n+1); for(int i=1;i<=n;i++){ a[i].quan=lower_bound(b+1,b+n+1,a[i].quan)-b; sum[i]=sum[i-1]+a[i].pin; } memset(f,0x3f,sizeof(f)); for(int i=1;i<=n+1;i++) for(int k=1;k<=n;k++) f[i][i-1][k]=0; for(int i=n;i>=1;i--) for(int j=i;j<=n;j++) for(int k=1;k<=n;k++) for(int t=i;t<=j;t++){ if(a[t].quan>=k) f[i][j][k]=min(f[i][j][k],f[i][t-1][a[t].quan]+f[t+1][j][a[t].quan]+sum[j]-sum[i-1]); f[i][j][k]=min(f[i][j][k],f[i][t-1][k]+f[t+1][j][k]+K+sum[j]-sum[i-1]); } cout<<f[1][n][1]<<endl; return 0; }
- 1
信息
- ID
- 1564
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 10
- 已通过
- 5
- 上传者