제출 #733786

#제출 시각아이디문제언어결과실행 시간메모리
733786myrcellaCopy and Paste 3 (JOI22_copypaste3)C++17
30 / 100
405 ms89620 KiB
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define ALL(x) x.begin(),x.end()
int lowbit(int x) {return x&(-x);}

const int maxn = 222;

int n;
ll A,B,C;
string s;
int a[maxn];
int len[maxn][maxn];
ll f[maxn][maxn][maxn],g[maxn][maxn];
ll ans[maxn*20];
pq <pair<pair<ll,int>,pii>,vector<pair<pair<ll,int>,pii>>,greater<pair<pair<ll,int>,pii>>> q;

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	memset(f,inf,sizeof(f));
	cin>>n>>s>>A>>B>>C;
	if (n>maxn) {
		ans[1] = A;
		rep(i,2,n+1) {
			ans[i] = i*A;
			rep(j,1,i) ans[i] = min(ans[i],ans[j] + B + C*(i/j) + A*(i%j));
		}
		cout<<ans[n];
		return 0;
	}
	rep(i,0,n) a[i] = (int)(s[i]-'a');
	rep(i,0,n)
		rep(j,i+1,n) {
			int x = i,y = j;
			while (y<n and a[x]==a[y]) x++,y++;
			len[i][j] = y-j; 
		}
	memset(f,inf,sizeof(f));
	memset(g,inf,sizeof(g));
	rep(i,0,n)
		rep(j,i,n) {
			g[i][j] = (j-i+1)*A + B;
			q.push({{g[i][j],-1},{i,j}});
		}
	while (!q.empty()) {
		if (q.top().fi.se==-1) { //g
			int i = q.top().se.fi, j = q.top().se.se;
			ll d = q.top().fi.fi;
			q.pop();
			if (g[i][j]!=d) continue;
			// update f
			if (f[i][j][j] > d + C) f[i][j][j] = d + C, q.push({{d+C,j},{i,j}});
			if (i-1>=0 and g[i-1][j] > d + A) g[i-1][j] = d + A, q.push({{d+A,-1},{i-1,j}});
		}
		else { //f
			int i = q.top().se.fi, j = q.top().se.se, k = q.top().fi.se;
			ll d = q.top().fi.fi;
			q.pop();
			if (f[i][j][k]!=d) continue;
			if (len[i][k+1] >= j-i+1 and f[i][j][k+j-i+1] > d + C) f[i][j][k+j-i+1] = d + C, q.push({{d+C,k+j-i+1},{i,j}});
			if (k+1<n and f[i][j][k+1] > d + A) f[i][j][k+1] = d + A, q.push({{d+A,k+1},{i,j}});
			if (g[i][k] > d + B) g[i][k] = d + B, q.push({{d+B,-1},{i,k}});
		}
	}
	ll ans = min(n*A,g[0][n-1] - B);
	rep(i,0,n) ans = min(ans,f[0][i][n-1]);
	cout<<ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...