题解 P5839 【[USACO19DEC]Moortal Cowmbat】
_虹_
2019-12-20 08:19:13
考虑将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;
}
```