Noble 的博客

Noble 的博客

♡虹蓝♡

题解 P5839 【[USACO19DEC]Moortal Cowmbat】

posted on 2019-12-20 08:19:13 | under 题解 |

考虑将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需要吸口氧。

#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;
}