题解 P5839 【[USACO19DEC]Moortal Cowmbat】

_虹_

2019-12-20 08:19:13

Solution

考虑将l-r换为颜色k,代价为cost_k(l,r) 显然可以转化为cost_k(1,r)-cost(1,l-1); 对于每种颜色k,最优的合法转移j,代价为dp[j]+cost_k(j,i)。 转移时枚举颜色取min. 当时发懒,直接写了堆,O(nmlogn),把堆换成变量可以O(nm) usaco过了,luogu需要吸口氧。 ```cpp #include <iostream> #include <string> #include <queue> #include <cstdio> using namespace std; #define int long long const int kmaxn=100000+5; const int kmaxm=30; int dp[kmaxn]; priority_queue<int,vector<int>,greater<int> > q[kmaxm]; int offset[kmaxm][kmaxn]; int a[kmaxm][kmaxm]; int n,m,K; string s; const int inf=1e9+7; #define T(x) (x-'a') signed main() { cin>>n>>m>>K; cin>>s; s=" "+s; for(int i=0;i<m;++i) { for(int j=0;j<m;++j) { cin>>a[i][j]; } } for(int k=0;k<m;k++) { for(int i=0;i<m;i++) { for(int j=0;j<m;j++) { a[i][j]=min(a[i][j],a[i][k]+a[k][j]); } } } for(int i=0;i<=n;++i) dp[i]=inf; for(int k=0;k<m;++k) { int cost=0; for(int i=1;i<=n;++i) { cost+=a[T(s[i])][k]; offset[k][i]=cost; } } for(int i=0;i<m;++i) q[i].push(0); for(int i=K,pre=1;i<=n;++i,++pre) { dp[i]=inf; for(int j=0;j<m;++j) { dp[i]=min(dp[i],q[j].top()+offset[j][i]); } for(int j=0;j<m;++j) { q[j].push(dp[pre]-offset[j][pre]); } } cout<<dp[n]<<endl; return 0; } ```