Submission #41624682

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const ll MAXN=110,INF=1e18;
void tomin(ll& x,ll y){x=min(x,y);}

ll n,k,c[MAXN],p[MAXN],pos[MAXN];

ll a[MAXN],m;

ll dp[MAXN][MAXN][MAXN],s[MAXN];

int main(){
	cin>>n>>k;
	rep(i,1,k)cin>>c[i];

	rep(i,1,n)cin>>p[i],pos[p[i]] = i;
	for(int l=1,r;l<=n;l=r+1){
		r=l;
		while(r+1 <= n && pos[r] < pos[r+1])r++;
		a[++m] = r-l+1;
	}

	rep(i,1,k+1)rep(a,0,m+1)rep(b,0,m+1)if(a<b)dp[i][a][b] = INF;

	rep(i,1,m)s[i] = s[i-1] + a[i];

	per(cur,k,1){
		rep(len,2,m){
			rep(i,1,m-len+1){
				int j=i+len-1;
				rep(l,i,j+1){
					tomin(dp[cur][i][j],c[cur] * (s[j]-s[l-1]) + dp[cur+1][i][l-1] + dp[cur+1][l][j]);
				}
			}
		}
	}

	ll ret = dp[1][1][m];
	if(ret==INF){
		cout<<"-1\n";
	}else{
		cout<<ret<<"\n";
	}
    return 0;
}

Submission Info

Judge Result